題目鏈接：

Codeforces741D

題目大意：給出一棵樹(shù)，根為$1$，每條邊有一個(gè)$a-v$的小寫(xiě)字母，求每個(gè)點(diǎn)子樹(shù)中的一條最長(zhǎng)的簡(jiǎn)單路徑使得這條路徑上的邊上的字母重排后是一個(gè)回文串。

顯然如果一條路徑上的字母重排后是回文串，那么最多有一個(gè)字母有奇數(shù)個(gè)。我們用$2^{22}$的一個(gè)二進(jìn)制來(lái)記錄有哪些字母有奇數(shù)個(gè)。剩下的只需要$dsu\ on\ tree$來(lái)求每個(gè)點(diǎn)的答案即可。對(duì)于每個(gè)點(diǎn)記錄它到根的路徑上的字母的二進(jìn)制狀態(tài)，顯然位于一個(gè)點(diǎn)兩個(gè)不同子樹(shù)中的點(diǎn)的狀態(tài)異或起來(lái)就是這兩個(gè)點(diǎn)間路徑的二進(jìn)制狀態(tài)。開(kāi)一個(gè)桶存每種狀態(tài)的最大深度然后在對(duì)于每個(gè)點(diǎn)求答案時(shí)依次遍歷子樹(shù)求出最大值即可。注意遍歷輕兒子時(shí)要先用輕兒子子樹(shù)中的點(diǎn)更新答案之后再將輕兒子子樹(shù)中的點(diǎn)的信息加入桶中。

#include<set> #include<map> #include<queue> #include<stack> #include<cmath> #include<cstdio> #include<bitset> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; int cnt[5000000]; int head[500010]; int to[1000010]; int nex[1000010]; int size[500010]; int son[500010]; int val[500010]; int dep[500010]; int tot; int n; int x,y; char ch[2]; int ans[500010]; int tag[500010]; void add(int x,int y) {nex[++tot]=head[x];head[x]=tot;to[tot]=y; } void dfs(int x) {size[x]=1;for(int i=head[x];i;i=nex[i]){dep[to[i]]=dep[x]+1;val[to[i]]^=val[x];dfs(to[i]);size[x]+=size[to[i]];if(size[to[i]]>size[son[x]]){son[x]=to[i];}} } void calc(int x,int anc) {ans[anc]=max(ans[anc],cnt[val[x]]+dep[x]-2*dep[anc]);for(int i=0;i<22;i++){ans[anc]=max(ans[anc],cnt[val[x]^(1<<i)]+dep[x]-2*dep[anc]);}for(int i=head[x];i;i=nex[i]){calc(to[i],anc);} } void solve(int x,int opt) {if(opt==1){cnt[val[x]]=max(dep[x],cnt[val[x]]);}else{cnt[val[x]]=-1<<30;}for(int i=head[x];i;i=nex[i]){solve(to[i],opt);} } void dsu_on_tree(int x,int opt) {for(int i=head[x];i;i=nex[i]){if(to[i]!=son[x]){dsu_on_tree(to[i],0);ans[x]=max(ans[x],ans[to[i]]);}}if(son[x]){dsu_on_tree(son[x],1);ans[x]=max(ans[x],ans[son[x]]);}cnt[val[x]]=max(cnt[val[x]],dep[x]);ans[x]=max(ans[x],cnt[val[x]]-dep[x]);for(int i=0;i<22;i++){ans[x]=max(ans[x],cnt[val[x]^(1<<i)]-dep[x]);}for(int i=head[x];i;i=nex[i]){if(to[i]!=son[x]){calc(to[i],x);solve(to[i],1);}}if(!opt){solve(x,-1);} } int main() {scanf("%d",&n);for(int i=2;i<=n;i++){scanf("%d%s",&x,ch);add(x,i);val[i]=1<<(ch[0]-'a');}dfs(1);for(int i=0;i<=(1<<22);i++){cnt[i]=-1<<30;}dsu_on_tree(1,1);for(int i=1;i<=n;i++){printf("%d ",ans[i]);} }

轉(zhuǎn)載于:https://www.cnblogs.com/Khada-Jhin/p/10645756.html

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專(zhuān)家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的[Codeforces741D]Arpa's letter-marked tree and Mehrdad's Dokhtar-kosh paths——dsu on tree的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。