Tree Constructer

题目：

题意：

如果点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]);
}