题解：P16710 愿望

结论

对于菊花图：若存在度数为n−1n-1n−1的点，则令非中心节点权值依次为0,1,2,…,n−20,1,2,\ldots,n-20,1,2,…,n−2，中心节点权值为000。

对于一般树：令树总异或和为0。给非根点分配互异子树异或和(0,1,…,n−2)(0,1,\dots,n-2)(0,1,…,n−2)，且父子不同（根为0）。DFS从小到大给儿子分配值，遇父值跳过。点权=自身目标值⊕\oplus⊕所有儿子目标值。

推导

我们考虑从子树异或和下手。

对于树TTT，节点iii的值为为aia_iai​，任意指定一个点为根rootrootroot。

我们定义XiX_iXi​为点iii的子树异或和，SSS为整棵树的异或和，题意为对于每一个点iii，由它的任意儿子vvv的XvX_vXv​与S⊕XiS\oplus X_iS⊕Xi​（即父亲那一块）的集合内的树互不相等。

我们先令S=0S=0S=0，那么父亲那一块值即为XiX_iXi​得：

-若iii非根，{Xv∣v∈son⁡(i)}∪{Xi}\{X_v\mid v\in\operatorname{son}(i)\}\cup\{X_i\}{Xv​∣v∈son(i)}∪{Xi​}中元素互异；

-若iii为根，{Xv∣v∈son⁡(i)}\{X_v\mid v\in\operatorname{son}(i)\}{Xv​∣v∈son(i)}中元素互异。

那么我们思考如何让XXX满足以上条件，显然可以的得到所有非根节点的值要彼此不同，我们可以使它们恰好覆盖1,2,…,n−11,2,\dots,n-11,2,…,n−1中的一些数，且父子之间不能相等。（规定Xroot=0X_{root}=0Xroot​=0即S=0S=0S=0）

我们可以发现非根节点有n−1n-1n−1个，我们可以用0,1,2,…,n−20,1,2,\dots,n-20,1,2,…,n−2来分配，来使得值域最小。

对于点iii，由XiX_iXi​定义：Xi=ai⊕X_i=a_i\oplusXi​=ai​⊕所有儿子的XXX得：ai=Xi⊕a_i=X_i\oplusai​=Xi​⊕所有儿子的XXX

容易证明这种构造方式的最大不会超过2⌈log⁡2n⌉2^{\lceil\log_2{n}\rceil}2⌈log2​n⌉（接近于nnn）。

但是当是菊花图时就可以卡到这个上线，可能超过m。

但显然菊花图只用令非中心节点权值依次为0,1,2,…,n−20,1,2,\ldots,n-20,1,2,…,n−2，中心节点权值为000就能构造出来。

实现

一遍深搜求XXX并且同时算出aaa就行了。

:::success[code]

#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;intn,m,a[1000001],deg[1000001];vector<int>g[1000001];voiddfs(intu,intfa,intw){intj=0,s=w;for(intv:g[u]){if(v==fa){continue;}if(j==w&&u!=1){j++;}s^=j;dfs(v,u,j);j++;}a[u]=s;}signedmain(){cin>>n>>m;for(inti=1;i<n;++i){intu,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);deg[u]++,deg[v]++;}intrt=0;for(inti=1;i<=n;++i){if(deg[i]==n-1){rt=i;}}if(rt){intj=0;for(inti=1;i<=n;++i){if(i!=rt){a[i]=j++;}}}else{dfs(1,0,0);}for(inti=1;i<=n;++i){cout<<a[i]<<"";}}

:::