Tree Constructer

正常人谁打正解啊
瞎搞了一个小时终于过了~~~~
由于是随机算法，不保证在规定时间内一定可以跑出答案（但是实测还是很快的）

建出的图一定是一个树
我们随便固定一个点为跟节点
先求一遍dfs序
然后就开始我们的随机算法
dfs跑树，随机赋值跑到的点的点权，保证和其父亲的或为m（m为1<<60 -1）
利用刚刚求出的dfs序，我们可以知道我们已经确定了哪些点，判断与他们的或不等于m
如果找不到点权匹配，返回0
如果接受递归返回0，以一定概率重新分配此点点权（我用的goto实现），以一定概率回溯到上一级

/*
随机搜索
固定一个点为根节点
跑树，保证相邻的点或为m
随机点权，以一定概率进行回溯 
*/ 
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int m=(1ll<<60)-1;
struct oppo{
    int to,nex;
}rod[10005];
int head[105],tot;
void add(int from,int to)
{
    rod[++tot].to=to;
    rod[tot].nex=head[from];
    head[from]=tot;
}
int rand_m()
{
    int ans=0;
    for(int i=0;i<=59;i++)
        ans+= (1ll*(rand()&1))<<i;
    return ans;
}
int val[105]; 
int ds[105],tt;
void ddd(int x,int fa)//求dfs序 
{
    ds[++tt]=x;
    for(int i=head[x];i;i=rod[i].nex){
        int to=rod[i].to;
        if(to==fa) continue;
        ddd(to,x);
    }
}
bool dfs(int x,int fa,int k)
{
    //随机自身点权 
    begin://重新开始标记 
    int tot=0;
    while(1){
        val[x]=(k^m)|rand_m();
        bool flag=0;
        for(int i=1;i<=n&&ds[i]!=x&&!flag;i++)
            if(ds[i]!=fa&&(val[ds[i]]|val[x])==m){
                flag=1;
            }
        if(!flag) break;
        if(++tot>100) return 0;//找不到可行值 
    }
    int all=0;
    //遍历子树 
    for(int i=head[x];i;i=rod[i].nex){
        int to=rod[i].to;
        if(to==fa) continue;
        if(!dfs(to,x,val[x])){
            if(rand()%5) goto begin;//重新开始分配此节点 
            else{
                val[x]=-1;
                return 0;
            }//向上返回 
        }
    }
    return 1;
}
signed main()
{
    srand(time(0));
    memset(val,-1,sizeof(val));
    cin>>n;
    for(int i=1;i<n;i++){
        int s,t;
        cin>>s>>t;
        add(s,t);
        add(t,s);
    }
    ddd(1,0);
    while(dfs(1,0,m)==0);
    for(int i=1;i<=n;i++)
        cout<<val[i]<<" ";
    return 0;
}