2020CCPC长春F[树上启发式合并+两两异或和拆位Trick]

2020CCPC长春F[树上启发式合并两两异或和拆位Trick]简单题意给定一颗有根树对于任意两点ij 如果a_i ^ a_j a_{lca(i,j)},那么对答案的贡献加i^j, 求解最终的答案题解对于树上信息不进行修改操作且对于一个节点来说统计一遍子树信息就可以得到该节点的答案的问题我们就可以采用树上启发式合并。这道题显然有这个特征而对于两两异或和我们想要快速求解也有一个trick维护所有合法答案的每一位上的1的数目以及0的数目那么最终的异或和就是每一位的cnt0 * cnt1 * 这一位对应的二进制权值那么有了以上的前置知识我们就可以对子树建立信息统计利用树上启发式合并完成这道题。我们维护子树中每个数字的数目以及每个数字的每一位的1的数目然后每当我们遍历到一个节点的时候枚举这个点作为lca我们需要找到两个子树中的点进行异或因此当我们遍历一颗子树的时候只能利用别的子树的信息而不能利用当前子树的信息所以我们可以进行两次遍历第一次遍历进行答案统计第二次遍历将子树节点统计进去而由于lca定值并且lca的权值我们需要知道如果采用传统的dfs遍历会导致我们还要传一个真正的lca参数我们可以采用dfn序遍历这样就会比dfs好写答案的统计对于u 作为lca的时候我们枚举子节点v1的时候需要找到其他节点中的权值为a_u^a_v1的其他节点进行答案统计对于每一位:如果这一位为1 那么我们加入cnt0 * 这一位如果是0那么我们加入cnt1 * 这一位code#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN2e55;constintMAXN120;voidsolve(){intn;cinn;vectorinta(n1,0);for(inti1;in;i){cina[i];}vectorvectorinte(n1);for(inti1;in;i){intu,v;cinuv;e[u].push_back(v);e[v].push_back(u);}vectorintson(n1,0);vectorintsz(n1,0),dfn(n1,0),row(n1,0);intcnts0;vectorinttot(MAXN,0);vectorvectorintcnt(MAXN,vectorint(21,0));autodfssz[](autoself,intu,intfa)-void{sz[u]1;dfn[u]cnts;row[cnts]u;for(autov:e[u]){if(vfa)continue;self(self,v,u);sz[u]sz[v];if(sz[v]sz[son[u]])son[u]v;}};dfssz(dfssz,1,0);intmaxn0;autoupd[](intu,intval)-void{intva[u];tot[v]val;for(intb0;b20;b){if((ub)1)cnt[v][b]val;}};intans0;autoquery[](intval,intx)-int{intres0;for(intb0;b20;b){intonescnt[val][b];if((xb)1){res1LL*(tot[val]-ones)*(1b);}elseres1LL*ones*(1b);}returnres;};autodfs[](autoself,intu,intfa,intkeep)-void{for(autov:e[u]){if(vfa||vson[u])continue;self(self,v,u,0);}if(son[u]!0){self(self,son[u],u,1);}for(autov:e[u]){if(v!fav!son[u]){for(intidfn[v];idfn[v]sz[v];i){intxrow[i];ansquery(a[u]^a[x],x);}for(intidfn[v];idfn[v]sz[v];i){upd(row[i],1);}}}upd(u,1);if(!keep){for(intidfn[u];idfn[u]sz[u];i){upd(row[i],-1);}}};dfs(dfs,1,0,0);coutans\n;}signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);intT1;// cinT;while(T--)solve();return0;}