正題

題目鏈接:https://www.luogu.com.cn/problem/P6623

---

題目大意

一棵樹，每個節點有一個權值$va{l}_i$，定義$di{s}_{i,j}$表示$i$到$j$的距離。

一個節點$x$的權值定義為該節點子樹中的每個節點$y$的$di{s}_{x,y}+va{l}_j$的異或和。

求所有節點的權值和

---

解題思路

對于一個二進制$01$串，我們可以用$Trie$從高位到低位存，我們記錄$Trie$上每個位置的答案，考慮如何讓整個$Trie$上的數字$+1$。

顯然對于一個$0$指向的節點，它會變成$1$，對于$1$指向的節點，它會變成$0$并且進位。也就是我們交換左右子樹后再向原來$1$指向的節點進位。

這樣我們就實現了一個可以插入數字或者全部$+1$來維護答案的數據結構，之后用樹上啟發式合并即可。

時間復雜度$O(n{\log }^{2}n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=6e5+10,M=27; struct node{int to,next; }a[N]; int n,tot,cnt,ls[N],siz[N],son[N]; int w[N],s[N*M],v[N*M],ch[N*M][2],ed[N*M],z; long long ans; void addl(int x,int y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot; } void Make(int &x,int k){if(!x){x=++cnt;ch[x][0]=ch[x][1]=s[x]=ed[x]=v[x]=0;}if(!k){s[x]^=1;ed[x]^=1;return;}Make(ch[x][k&1],k>>1);s[x]=s[ch[x][0]]^s[ch[x][1]]^ed[x];v[x]=(v[ch[x][0]]<<1)^((v[ch[x][1]]<<1)|s[ch[x][1]]);return; } void Merge(int x){if(!x){return;}swap(ch[x][0],ch[x][1]);if(ed[x]&&!ch[x][1]){ch[x][1]=++cnt;ch[cnt][0]=ch[cnt][1]=s[cnt]=ed[cnt]=v[cnt]=0;}ed[ch[x][1]]^=ed[x];s[ch[x][1]]^=ed[x];ed[x]=0;Merge(ch[x][0]);s[x]=s[ch[x][0]]^s[ch[x][1]]^ed[x];v[x]=(v[ch[x][0]]<<1)^((v[ch[x][1]]<<1)|s[ch[x][1]]);return; } void dfs(int x){siz[x]=1;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;dfs(y);siz[x]+=siz[y];if(siz[y]>siz[son[x]])son[x]=y;}return; } void calc(int x,int dep){Make(z,w[x]+dep);for(int i=ls[x];i;i=a[i].next){int y=a[i].to;calc(y,dep+1);}return; } void solve(int x){for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==son[x])continue;solve(y);}cnt=z=0;if(son[x])solve(son[x]),Merge(z);for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==son[x])continue;calc(y,1);}Make(z,w[x]);ans+=v[1];return; } int main() {freopen("tree2.in","r",stdin);scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&w[i]);for(int i=2;i<=n;i++){int x;scanf("%d",&x);addl(x,i);}dfs(1);solve(1);printf("%lld",ans); }

總結

以上是生活随笔為你收集整理的P6623-[省选联考2020A卷]树【Trie,树上启发式合并】的全部內容，希望文章能夠幫你解決所遇到的問題。

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