題目鏈接

　　狀態奇差無比，sbt都能錯一遍。

　　不動筆光想沒有想到怎么做，畫圖之后發現一個很明顯的性質……

　　那就是兩個開戰的部落，其中一個是另一個的父親。

　　所以在兒子那里加個權值。查詢的時候樹鏈剖分查詢鏈上點權和，減去lca的點權（因為lca那如果有點權，代表的是lca和lca的父親之間的那條邊）。

　　

#include<cstdio> #include<algorithm> #include<cctype> #include<cstring> #include<cstdlib> #define left (rt<<1) #define right (rt<<1|1) #define mid ((l+r)>>1) #define lson l,mid,left #define rson mid+1,r,right #define maxn 300050 using namespace std; inline long long read(){long long num=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)){num=num*10+ch-'0';ch=getchar();}return num*f; }struct Edge{int next,to; }edge[maxn*3]; int head[maxn],num; inline void add(int from,int to){edge[++num]=(Edge){head[from],to};head[from]=num; }int tree[maxn*4]; int dfn[maxn]; int deep[maxn]; int father[maxn]; int size[maxn]; int top[maxn]; int son[maxn]; int ID,n,m;void unifnd(int x,int fa){deep[x]=deep[fa]+1; size[x]=1;for(int i=head[x];i;i=edge[i].next){int to=edge[i].to;if(to==fa) continue;father[to]=x;unifnd(to,x);size[x]+=size[to];if(son[x]==0||size[son[x]]<size[to]) son[x]=to;} }void unionn(int x,int Top){dfn[x]=++ID; top[x]=Top;if(son[x]==0) return;unionn(son[x],Top);for(int i=head[x];i;i=edge[i].next){int to=edge[i].to;if(to==father[x]||to==son[x]) continue;unionn(to,to);} }inline void pushup(int rt){tree[rt]=tree[left]+tree[right]; }void update(int o,int num,int l,int r,int rt){if(l==r){tree[rt]+=num;return;}if(o<=mid) update(o,num,lson);else update(o,num,rson);pushup(rt);return; }int query(int from,int to,int l,int r,int rt){if(from<=l&&to>=r) return tree[rt];int ans=0;if(from<=mid) ans+=query(from,to,lson);if(to>mid) ans+=query(from,to,rson);return ans; }struct War{int from,to; }q[maxn];int cnt;inline void adds(int from,int to){if(deep[from]<deep[to]) swap(from,to);q[++cnt]=(War){from,to};update(dfn[from],1,1,n,1);return; }inline void del(int rnk){int from=q[rnk].from;update(dfn[from],-1,1,n,1); }inline int LCA(int from,int to){while(top[from]!=top[to]){if(deep[top[from]]<deep[top[to]]) swap(from,to);from=father[top[from]];}if(deep[from]>deep[to]) swap(from,to);return from; }inline int ask(int from,int to){int lca=LCA(from,to),ans=-query(dfn[lca],dfn[lca],1,n,1);while(top[from]!=top[to]){if(deep[top[from]]<deep[top[to]]) swap(from,to);ans+=query(dfn[top[from]],dfn[from],1,n,1);if(ans>0) return 0;from=father[top[from]];}if(deep[from]>deep[to]) swap(from,to);ans+=query(dfn[from],dfn[to],1,n,1);if(ans>0) return 0;return 1; }int main(){n=read(),m=read();for(int i=1;i<n;++i){int x=read(),y=read();add(x,y);add(y,x);}unifnd(1,1);unionn(1,1);for(int i=1;i<=m;++i){char c[10];scanf("%s",c);if(c[0]=='Q'){int x=read(),y=read();if(ask(x,y)) printf("Yes\n");else printf("No\n");}else if(c[0]=='C'){int x=read(),y=read();adds(x,y);}else{int x=read();del(x);}}return 0; }

?

轉載于:https://www.cnblogs.com/cellular-automaton/p/8387305.html

總結

以上是生活随笔為你收集整理的【Luogu】P3950部落冲突（树链剖分）的全部內容，希望文章能夠幫你解決所遇到的問題。

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