正常人谁打正解啊
瞎搞了一个小时终于过了~~~~
由于是随机算法,不保证在规定时间内一定可以跑出答案(但是实测还是很快的)
建出的图一定是一个树
我们随便固定一个点为跟节点
先求一遍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; }