题号 NC216183
名称 Tree Constructer
来源 第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（济南）
戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情
欢迎给每日一题投稿，投稿需要提供牛客题库里的题目+题解 投稿有牛币奖励，可发站内信给王清楚或联系QQ 234186389
每日一题QQ群:659028468

题解

作者：回归梦想

题意：

如果点x和y有连边，当且仅当a[x] or a[y] = 2^60^ - 1 （两者是充分必要）
现在给你边的关系，问你每个点的值应该是多少？（给出一种情况即可）

题解：

构造题，思路非常巧妙
2^60^就是（1<<60）,减去1也就是从第一位到第59位都是1（第六十位是0省略了）
首先01染色，将点分为黑点和白点，让白色的点为个数少一些的
选数量较少的一组是确保数量小于等于 50
现在每个点都要节点编号id和颜***r>id为该点的编号
对于白色的点，我们让其最高位为0，让其第id位也是0，其余位置都是1
对于黑色，我们让其最高位是1，与它相邻的所有点（也就是白点）的第id位置为1，其余为0

我们来分析分析为什么这样构造是对的
因为所有白色的最高位是0，所以确保了所有白色之间没有边。
白色的点第id为也是0，而与它相邻的黑点第id位是1，两者首位也是0和1，正好or后就是2^60^ - 1，这就是确保了黑色与所哟相邻的白色节点满足条件
因为黑点除了首位，只要相邻的白点的第id位是1，所有当一个白点与该黑点不相连时，黑点给不了白点所需要位置上的1

综上所述就是：黑点所多的（也就是1的部分）是相邻白点所缺的位置
这个构图不禁让人感叹，妙啊~~

代码：

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);
   return s*w;
}
const int maxn=400;
ll ans[maxn],id[maxn];
vector<int>g[maxn],color[2];
void dfs(int x,int fa,int col)
{
    color[col].push_back(x);
    for(auto v:g[x])
    {
        if(v==fa)continue;
        dfs(v,x,col^1);
    }
}
int main()
{
    //cout<<((12312312-2)|1);
    int n;
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0,1);//染色过程
    if(color[0].size()>color[1].size())swap(color[0],color[1]);//然后白色为少的 
    for(int i=0;i<color[0].size();i++)//对于白色 
    {
        int v=color[0][i];
        ans[v]=(1ll<<60)-1-(1ll<<59)-(1ll<<i);
        id[v]=i;
    }

    for(int i=0;i<color[1].size();i++)
    {
        int u=color[1][i];
        ll tmp=(1ll<<59);//首位是1
        for(auto v:g[u])
        {
            tmp+=(1ll<<id[v]);//与第v位相连，该点编号是id[v] 
        } 
        ans[u]=tmp;
        id[u]=i;
    }
    for(int i=1;i<=n;i++)
        if(i==1) printf("%lld",ans[i]);
        else printf(" %lld",ans[i]);
}

欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目2月20日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴