题解：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​即父亲那一块的集合内的树互不相等。我们先令S0S0S0那么父亲那一块值即为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中的一些数且父子之间不能相等。规定Xroot0X_{root}0Xroot​0即S0S0S0我们可以发现非根节点有n−1n-1n−1个我们可以用0,1,2,…,n−20,1,2,\dots,n-20,1,2,…,n−2来分配来使得值域最小。对于点iii由XiX_iXi​定义Xiai⊕X_ia_i\oplusXi​ai​⊕所有儿子的XXX得aiXi⊕a_iX_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]#includebits/stdc.h#defineintlonglongusingnamespacestd;intn,m,a[1000001],deg[1000001];vectorintg[1000001];voiddfs(intu,intfa,intw){intj0,sw;for(intv:g[u]){if(vfa){continue;}if(jwu!1){j;}s^j;dfs(v,u,j);j;}a[u]s;}signedmain(){cinnm;for(inti1;in;i){intu,v;cinuv;g[u].push_back(v);g[v].push_back(u);deg[u],deg[v];}intrt0;for(inti1;in;i){if(deg[i]n-1){rti;}}if(rt){intj0;for(inti1;in;i){if(i!rt){a[i]j;}}}else{dfs(1,0,0);}for(inti1;in;i){couta[i];}}:::