Jamie and Tree[CF916E]

題意：

有一棵n個點的樹，每個節點上有一個權值wi，最開始根為1號點．現在有3種
類型的操作：
? 1 root, 表示將根設為root.
? 2 u v x, 設u, v的最近公共祖先為p, 將p的子樹中的所有點的權值加上x.
? 3 u, 查詢u的子樹中的所有點的權值和．
對于每個3操作，輸出答案．

題解：

須知知識：線段樹，樹鏈剖分

如果真的換根太麻煩了，所以我們每次只記錄新根，并看看新根在后續操作中會有什么影響

如果在沒有換根的情況下，操作2很容易實現，但是因為現在root已經發生改變所以我們需要特判。
lca1=lca（u,v）
lca2=lca(root,v)
lca3=lca(root,u)
lca=max(dep[lca1],dep[lca2],dep[lca3])
我們要先記錄lca1，lca2，lca3中dep最深的
如果root不在lca的子樹里，那直接在區間[l[lca],r[lca]]內更新x即可
如果root等于lca，那么就是全樹更新
如果root在lca的子樹上，先把整個樹更新，然后找到root到lca的路徑與lca的兒子節點，更新子樹-x
相當于先全部+x，然后將不需要修改的部分再-x

if(root==lca1)tree.update(1,1,n,1,n,x);else if(dfn[rt]<dfn[lca1]||dfn[rt]>dfn[lca1]+size[lca1]-1)tree.update(1,1,n,dfn[lca1],dfn[lca1]+size[lca1]-1,x);else {lca1=change(lca1);tree.update(1,1,n,1,n,x);tree.update(1,1,x,dfn[lca1],dfn[lca1]+size[lca1]-1,-x);}

對于操作三，我們要判斷root與v的關系，如果root不在v的子樹上，那就正常操作sum(l[v],r[v])
如果root就是v，更新整個子樹
但如果root在v的子樹上，那么其實和操作2的第三個情況類似，先求所以樹的權值，然后減去不需要算的部分。這里不需要算的部分是root到lca的路徑與lca的兒子節點X
（為什么是這個點？看著圖仔細想想）

if(u==rt)sum=tree.query(1,1,n,1,n); else if(dfn[rt]<dfn[u]||dfn[rt]>dfn[u]+size[u]-1)sum=tree.query(1,1,n,dfn[u],dfn[u]+size[u]-1); else {u=change(u);sum+=tree.query(1,1,n,1,n);sum-=tree.query(1,1,n,dfn[u],dfn[u]+size[u]-1);}

代碼：

#include<bits/stdc++.h>#define REP(i,a,b) for(int i=a;i<=b;++i) typedef long long ll; using namespace std;template<typename T>void read(T &x){T _=0,mul=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')mul=-1;ch=getchar();}while(isdigit(ch))_=(_<<1)+(_<<3)+(ch^'0'),ch=getchar();x=_*mul; }const int maxn=3e5+10;struct Segment_Tree{ #define mid ((l+r)>>1) #define lc (rt<<1) #define rc (rt<<1|1) #define lson lc,l,mid #define rson rc,mid+1,rll sum[maxn<<2],tag[maxn<<2];void pushdown(int rt,int l,int r){sum[lc]+=tag[rt]*(mid-l+1);tag[lc]+=tag[rt];sum[rc]+=tag[rt]*(r-mid); tag[rc]+=tag[rt];tag[rt]=0;}void update(int rt,int l,int r,int L,int R,ll x){if(L<=l && r<=R){sum[rt]+=(r-l+1)*x;tag[rt]+=x;return;}if(tag[rt])pushdown(rt,l,r);if(L<=mid)update(lson,L,R,x);if(R>=mid+1)update(rson,L,R,x);sum[rt]=sum[lc]+sum[rc];}ll query(int rt,int l,int r,int L,int R){if(L<=l && r<=R)return sum[rt];ll ret=0ll;if(tag[rt])pushdown(rt,l,r);if(L<=mid)ret+=query(lson,L,R);if(R>=mid+1)ret+=query(rson,L,R);return ret;} }T;int n,q,root,w[maxn],cnt; int to[maxn<<1],last[maxn<<1],beg[maxn],cnte; int fa[maxn],son[maxn],top[maxn],siz[maxn],dep[maxn],cnt_dfn,dfn[maxn];void add(int u,int v){last[++cnte]=beg[u];beg[u]=cnte;to[cnte]=v; }void dfs1(int u,int f){fa[u]=f;siz[u]=1;dep[u]=dep[f]+1;for(int i=beg[u];i;i=last[i]){if(to[i]==f)continue;dfs1(to[i],u);siz[u]+=siz[to[i]];if(siz[to[i]]>siz[son[u]])son[u]=to[i];} }void dfs2(int u,int t){dfn[u]=++cnt_dfn;top[u]=t;if(son[u])dfs2(son[u],t);for(int i=beg[u];i;i=last[i]){if(to[i]==fa[u] || to[i]==son[u])continue;dfs2(to[i],to[i]);} }int find(int u,int v){while(top[u]!=top[v]){++cnt;if(dep[top[u]]<dep[top[v]])swap(u,v);u=fa[top[u]];}return dep[u]<dep[v] ? u : v; }int change(int u){int v=root;while(top[v]!=top[u]){if(fa[top[v]]==u)return top[v];v=fa[top[v]];}return son[u]; }void init(){read(n); read(q);root=1;REP(i,1,n)read(w[i]);REP(i,1,n-1){int u,v;read(u); read(v);add(u,v);add(v,u);}dfs1(1,0);dfs2(1,1);REP(i,1,n)T.update(1,1,n,dfn[i],dfn[i],w[i]); }int main(){init();REP(i,1,q){int ty,u,v;ll x;read(ty);if(ty==1){read(u);root=u;}else if(ty==2){read(u); read(v); read(x);int lca=find(u,v),tmp;if(dep[tmp=find(u,root)]>dep[lca])lca=tmp;if(dep[tmp=find(v,root)]>dep[lca])lca=tmp;if(lca==root)T.update(1,1,n,1,n,x);else if(dfn[root]<dfn[lca] || dfn[root]>dfn[lca]+siz[lca]-1)T.update(1,1,n,dfn[lca],dfn[lca]+siz[lca]-1,x);else{lca=change(lca);T.update(1,1,n,1,n,x);T.update(1,1,n,dfn[lca],dfn[lca]+siz[lca]-1,-x);}}else{ll sum=0ll;read(u);if(u==root)sum=T.query(1,1,n,1,n);else if(dfn[root]<dfn[u] || dfn[root]>dfn[u]+siz[u]-1)sum=T.query(1,1,n,dfn[u],dfn[u]+siz[u]-1);else{u=change(u);sum+=T.query(1,1,n,1,n);sum-=T.query(1,1,n,dfn[u],dfn[u]+siz[u]-1);}cout<<sum<<endl;}}return 0; }

總結

以上是生活随笔為你收集整理的Jamie and Tree[CF916E]的全部內容，希望文章能夠幫你解決所遇到的問題。

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