正題

評測記錄:https://www.luogu.org/recordnew/lists?uid=52918&pid=CF741D

---

題目大意

一棵根為$1$的樹，每條邊上有一個字符$(a?v$共$22$種$)$。 一條簡單路徑被稱為$Dokhtar?kosh$當且僅當路徑上的字符經過重新排序后可以變成一個回文串。 求每個子樹中最長的$Dokhtar?kosh$路徑的長度。

---

解題思路

對于一堆重新排列后可以變成回文串的字母，僅當只有少于2個字母出現了奇數次。所以就只需要記錄奇偶問題，我們可以狀壓一下。
求出從根到每個點的值，之后x到y的路徑就可以表示為$w_{x}xor{w}_y$，因為$LCA$之上的都會相互抵消。

我們得到$O(n^{2}logn)$的做法。之后用樹上啟發式合并就可以變為$O(nlo{g}^{2}n)$

---

$code$

#include<cstdio> #include<algorithm> #define N 500010 using namespace std; struct node{int to,next,w; }a[N]; int tot,ls[N],size[N],dep[N],val[N]; int len[1<<22],ans[N],dfn[N],rfn[N],ed[N]; int cnt,n,son[N],dpt[N]; void addl(int x,int y,int w)//加邊 {a[++tot].to=y;a[tot].next=ls[x];a[tot].w=w;ls[x]=tot; } void dfs(int x)//第一次搜索需要信息 {size[x]++;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;dep[y]=dep[x]+1;val[y]=val[x]^(1<<a[i].w);dfs(y);if(size[y]>size[son[x]])son[x]=y;size[x]+=size[y];} } int get_ans(int x)//計算從x出發的最長路徑長度 {int ans=0;if(len[val[x]])ans=dep[x]+len[val[x]];for(int i=0;i<22;i++)if(len[val[x]^(1<<i)])ans=max(ans,dep[x]+len[val[x]^(1<<i)]);return ans; } void dus(int x,int top)//樹上啟發式合并 {dfn[++cnt]=x;rfn[x]=cnt;for(int i=ls[x];i;i=a[i].next)//搜索除了最大的子樹if(a[i].to!=son[x]){dus(a[i].to,a[i].to);ans[x]=max(ans[x],ans[a[i].to]);}int mid=cnt;if(son[x])//搜索最大的子數{dus(son[x],top);ans[x]=max(ans[x],ans[son[x]]);}ed[x]=cnt;for(int i=rfn[x]+1;i<=mid;i=ed[dfn[i]]+1)//枚舉子樹{for(int j=i;j<=ed[dfn[i]];j++)//掃描這個子樹的答案ans[x]=max(ans[x],get_ans(dfn[j])-2*dep[x]);for(int j=i;j<=ed[dfn[i]];j++)//將這個子樹加入可掃描答案len[val[dfn[j]]]=max(len[val[dfn[j]]],dep[dfn[j]]);//分兩次for不會使得起點和終點在同一棵子樹}ans[x]=max(ans[x],get_ans(x)-2*dep[x]);//自己為起點len[val[x]]=max(len[val[x]],dep[x]);//更新if(x==top)//不保留該子樹信息for(int i=rfn[x];i<=ed[x];i++)len[val[dfn[i]]]=0; } int main() {scanf("%d",&n);for(int i=2;i<=n;i++){int x;scanf("%d",&x);char c=getchar(); while (c<'a'||c>'v') c=getchar();addl(x,i,c-'a');}dep[0]=-1;dfs(1);dus(1,1);for(int i=1;i<=n;i++)printf("%d ",ans[i]); } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的CF741D-Arpa's letter-marked tree and Mehrdad's Dokhtar-kosh paths【树上启发式合并】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。