正題

---

題目大意

一棵樹(shù)，開(kāi)始全是白點(diǎn)，兩個(gè)操作

將一個(gè)節(jié)點(diǎn)翻轉(zhuǎn)

詢問(wèn)一顆棋子與所有面朝上為黑色的棋子lca最深的那個(gè)的編號(hào)

---

解題思路

必備技能：平衡樹(shù)（或set庫(kù)的使用方法），大量卡常技巧，LCA

我們可以發(fā)現(xiàn)和一個(gè)點(diǎn)的lca最深的話，這個(gè)點(diǎn)一定是在dfs序上最近的點(diǎn)，這時(shí)候我們就要使用平衡樹(shù)了。
每多一個(gè)黑點(diǎn)就將dfs序加入平衡樹(shù)，刪除就去掉。然后詢問(wèn)一個(gè)點(diǎn)的時(shí)候就在平衡樹(shù)上查詢離他dfs最近的一個(gè)黑點(diǎn)，然后求LCA。
這里就不敲平衡樹(shù)了，反正set也行

不過(guò)直接用dfs會(huì)爆炸，所以要用奇特的方法計(jì)算dfs序。

---

code

注意：以下代碼包含大量卡常操作，如果對(duì)您的眼睛造成了傷害那我表示道歉。

#pragma GCC optimize("O2") #include<cstdio> #include<algorithm> #include<set> #include<cmath> #include<queue> #include<cctype> #define N 800010 using namespace std; struct line{int to,next,w; }a[N]; int tot,n,m,x,y,ls[N],dep[N],t,cnt,T,que[N]; int dfn[N],put[N],f[N][24],dis[N][24],siz[N]; set<int> s; queue<int> q; __attribute__((optimize("O3"))) inline int read() {int x=0,f=1; char c=getchar();while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();return x*f; } __attribute__((optimize("O3"))) inline void addl(int x,int y) {a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot; } __attribute__((optimize("O3"))) void dfs()//求dfs序 {int h=0,t=1;que[++h]=1;dfn[1]=1; put[dfn[1]]=1;while(h<=t) {int x=que[h++],last=x;for(register int i=ls[x];i;i=a[i].next){int y=a[i].to;dfn[y]=dfn[last]+(last!=x?siz[last]:1);put[dfn[y]]=y;que[++t]=y;last=y;}} } __attribute__((optimize("O3"))) void bfs(int s)//預(yù)處理LCA {int h=0,t=1;que[++h]=1;while(h<=t) {int x=que[h++];siz[x]=1;for(register int i=ls[x];i;i=a[i].next) {int y=a[i].to;dep[y]=dep[x]+1,f[y][0]=x;que[++t]=y;}}for(register int i=n;i>=1;i--)siz[f[que[i]][0]]+=siz[que[i]];T=(int)(log(n)/log(2))+1;for (int j=1;j<=T;j++){for (int i=1;i<=n;i++){f[i][j]=f[f[i][j-1]][j-1];dis[i][j]=min(dis[i][j-1],dis[f[i][j-1]][j-1]);}}cnt=0; } __attribute__((optimize("O3"))) int LCA(int x,int y)//求LCA {if (dep[x]>dep[y]) swap(x,y);for (int i=T;i>=0;i--)if (dep[f[y][i]]>=dep[x]) y=f[y][i];if (x==y) return x;for (int i=T;i>=0;i--)if (f[y][i]!=f[x][i]) {x=f[x][i];y=f[y][i];}return f[x][0]; } __attribute__((optimize("O3"))) void print(int x){if (x>9) print(x/10); putchar(x%10+48); return; } __attribute__((optimize("O3"))) signed main() {n=read();m=read();for(register int i=2;i<=n;i++){addl(read(),i);}bfs(1);dfs();dep[0]=-1;for(register int i=1;i<=m;i++){x=read();if(x>0){if(!s.insert(dfn[x]).second) s.erase(dfn[x]);//加點(diǎn)or去點(diǎn)}else{x=abs(x);int t1=0,t2=0;set<int>::iterator y=s.lower_bound(dfn[x]);if(y!=s.end()) t1=LCA(x,put[*y]);if(y!=s.begin()) y--,t2=LCA(x,put[*y]);if(dep[t1]<dep[t2]) print(t2),putchar('\n');else print(t1),putchar('\n');}//求最近的} }

總結(jié)

以上是生活随笔為你收集整理的nssl1164-观察【平衡树,LCA】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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