正題

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

---

題目大意

給出$n$個(gè)點(diǎn)的一棵有根三叉樹(shù)，保證每個(gè)點(diǎn)的兒子個(gè)數(shù)為$3$或者$0$，每個(gè)葉子有一個(gè)權(quán)值$0$或$1$，每個(gè)非葉子節(jié)點(diǎn)的權(quán)值是它兒子中權(quán)值較多的那個(gè)，每次修改一個(gè)葉子的權(quán)值，求根節(jié)點(diǎn)的權(quán)值。

$1\le n,q\le 5\times 10^5$

---

解題思路

修改一個(gè)節(jié)點(diǎn)會(huì)影響的權(quán)值顯然是它到根節(jié)點(diǎn)路徑上的一個(gè)前綴。

然后考慮什么樣的節(jié)點(diǎn)會(huì)受到影響，如果$0$改為$1$那么一路上原來(lái)恰好為兩個(gè)$0$的節(jié)點(diǎn)就會(huì)被修改，那么我們的思路是考慮找到這條路徑上第一個(gè)$1$的個(gè)數(shù)不為$1$的節(jié)點(diǎn)。

而且考慮上修改的話十分的麻煩，因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$O(n{\log }^{2}n)$過(guò)不去所以不考慮樹(shù)剖，可以考慮一下$LCT$。

我們可以先聯(lián)通修改點(diǎn)到根的節(jié)點(diǎn)，然后在$Splay$上二分出第一個(gè)不為$1$的節(jié)點(diǎn)，然后對(duì)于它和它的右子樹(shù)暴力修改即可。

$1$改為$0$同理，維護(hù)第一個(gè)不為$2$的節(jié)點(diǎn)即可。

時(shí)間復(fù)雜度$O(n\log n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<stack> using namespace std; const int N=2e6+10; int n,m,ans,fa[N],v[N],w1[N],w2[N],lazy[N],t[N][2]; vector<int> G[N];stack<int> s; bool Nroot(int x) {return fa[x]&&(t[fa[x]][0]==x||t[fa[x]][1]==x);} bool Direct(int x) {return t[fa[x]][1]==x;} void PushUp(int x){if(w1[t[x][1]])w1[x]=w1[t[x][1]];else if(v[x]!=1)w1[x]=x;else w1[x]=w1[t[x][0]];if(w2[t[x][1]])w2[x]=w2[t[x][1]];else if(v[x]!=2)w2[x]=x;else w2[x]=w2[t[x][0]];return; } void PushR(int x,int w) {v[x]^=3;swap(w1[x],w2[x]);lazy[x]+=w;return;} void PushDown(int x){if(!lazy[x])return;PushR(t[x][0],lazy[x]);PushR(t[x][1],lazy[x]);lazy[x]=0;return; } void Rotate(int x){int y=fa[x],z=fa[y];int xs=Direct(x),ys=Direct(y);int w=t[x][xs^1];if(Nroot(y))t[z][ys]=x;t[x][xs^1]=y;t[y][xs]=w;if(w)fa[w]=y;fa[y]=x;fa[x]=z;PushUp(y);PushUp(x);return; } void Splay(int x){int y=x;s.push(x);while(Nroot(y))y=fa[y],s.push(y);while(!s.empty())PushDown(s.top()),s.pop();while(Nroot(x)){y=fa[x];if(!Nroot(y))Rotate(x);else if(Direct(x)==Direct(y))Rotate(y),Rotate(x);else Rotate(x),Rotate(x);}return; } void Access(int x){for(int y=0;x;y=x,x=fa[x])Splay(x),t[x][1]=y,PushUp(x);return; } void Updata(int x){int op=(v[x]^=2);x=fa[x];Access(x);Splay(x);if(op){if(w1[x]){x=w1[x];Splay(x);PushR(t[x][1],1);PushUp(t[x][1]);v[x]++;PushUp(x);}else ans=!ans,PushR(x,1),PushUp(x);}else{if(w2[x]){x=w2[x];Splay(x);PushR(t[x][1],-1);PushUp(t[x][1]);v[x]--;PushUp(x);}else ans=!ans,PushR(x,-1),PushUp(x);}return; } void dfs(int x){for(int i=0;i<G[x].size();i++){int y=G[x][i];dfs(y);v[x]+=(v[y]>>1);}PushUp(x);return; } int main() {scanf("%d",&n);for(int i=1;i<=n;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);fa[x]=fa[y]=fa[z]=i;G[i].push_back(x);G[i].push_back(y);G[i].push_back(z);}for(int i=n+1;i<=3*n+1;i++)scanf("%d",&v[i]),v[i]<<=1;dfs(1);ans=v[1]>>1;scanf("%d",&m);while(m--){int x;scanf("%d",&x);Updata(x);printf("%d\n",ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的P4332-[SHOI2014]三叉神经树【LCT】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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