看到换根果断lct啊，然而其实我板子还没有打熟，还不会维护子树信息，于是就挂掉了……
然而正解并不是lct。
其实好像很久很久以前将lca的时候好像讲到过一道换根的题，当时没有听懂。
直接说正解吧：
把dfs序搞出来用线段树维护。
用一个变量记录当前根节点，操作一直接改就行了。
然后是操作三：
分情况讨论，设当前根节点为root，询问的点为a。
如果root不在a的子树内，那么root不会影响a的子树，仍然输出1为根时的子树和就行了。
如果在子树内，
如图，如果要查询1的子树和，那么找到1与root这条链上靠近1的点，整体的和减去这个点的子树和就是了。（感性理解一下。）
那么这个点怎么求呢？只需要对于每个点把与他直接相连的儿子的dfs序塞到一个vector里，upper_bound然后-1就可以了。
操作二：
首先求出以1为根是a，b两点的lca。
与操作三类似，如果root不在lca的子树内，那么root不会影响lca，直接加就行。
如果在子树内，那么找a，b与root的lca中深度较大的那个。
之后就和操作三一样了。
1 #include<algorithm> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #define LL long long 7 #define re register 8 #define co const 9 #define rec re co 10 #define inline __attribute((always_inline)) 11 const int LLL=1<<20|1; 12 char buffer[LLL],*S,*TT; 13 #define getchar() ((S==TT&&(TT=(S=buffer)+fread(buffer,1,LLL,stdin),S==TT))?EOF:*S++) 14 using namespace std; 15 struct edge 16 { 17 int u,v,nxt; 18 #define u(x) ed[x].u 19 #define v(x) ed[x].v 20 #define n(x) ed[x].nxt 21 }ed[1000010]; 22 int first[300010],num_e; 23 #define f(x) first[x] 24 int n,q,w[300010]; 25 bool pd2=1,pd3=1; 26 vector<int> inc[300010]; 27 LL fa[300010][21],dep[300010]; 28 int dfn[300010],id[300010],cnt,L[300010],R[300010];LL res; 29 int siz[300010],son[300010],top[300010]; 30 void dfs1(int x) 31 { 32 siz[x]=1; 33 for(int i=f(x);i;i=n(i)) 34 if(v(i)!=fa[x][0]) 35 { 36 fa[v(i)][0]=x;dep[v(i)]=dep[x]+1; 37 dfs1(v(i));siz[x]+=siz[v(i)]; 38 if(siz[v(i)]>siz[son[x]])son[x]=v(i); 39 } 40 } 41 void dfs2(int x,int t) 42 { 43 top[x]=t;dfn[x]=++cnt;id[cnt]=x;L[x]=cnt; 44 if(son[x])dfs2(son[x],t),inc[x].push_back(dfn[son[x]]); 45 for(int i=f(x);i;i=n(i)) 46 if(v(i)!=fa[x][0]&&v(i)!=son[x]) 47 dfs2(v(i),v(i)),inc[x].push_back(dfn[v(i)]); 48 R[x]=cnt; 49 } 50 inline int LCA(int x,int y) 51 { 52 while(top[x]!=top[y]) 53 { 54 if(dep[top[x]]>dep[top[y]])swap(x,y); 55 y=fa[top[y]][0]; 56 } 57 if(dep[x]>dep[y])swap(x,y); 58 return x; 59 } 60 struct xjs_Tree 61 { 62 struct tree 63 { 64 int l,r;LL sum,la; 65 #define l(x) tr[x].l 66 #define r(x) tr[x].r 67 #define la(x) tr[x].la 68 #define sum(x) tr[x].sum 69 #define ls(x) ((x)<<1) 70 #define rs(x) (ls(x)+1) 71 }tr[8000000]; 72 void build(rec int x,rec int l,rec int r) 73 { 74 l(x)=l,r(x)=r,la(x)=0; 75 if(l==r){sum(x)=w[id[l]];return;} 76 int mid=(l+r)>>1; 77 build(ls(x),l,mid); 78 build(rs(x),mid+1,r); 79 sum(x)=sum(ls(x))+sum(rs(x)); 80 } 81 inline void down(rec int x) 82 { 83 if(l(x)==r(x))return; 84 if(!la(x))return; 85 sum(ls(x))+=(r(ls(x))-l(ls(x))+1)*la(x); 86 sum(rs(x))+=(r(rs(x))-l(rs(x))+1)*la(x); 87 la(ls(x))+=la(x);la(rs(x))+=la(x);la(x)=0; 88 } 89 void add(rec int x,rec int l,rec int r,rec LL y) 90 { 91 if(l>r)return; 92 down(x); 93 if(l(x)>=l&&r(x)<=r) 94 { 95 sum(x)+=(r(x)-l(x)+1)*y; 96 la(x)+=y;return; 97 } 98 int mid=(l(x)+r(x))>>1; 99 if(l<=mid)add(ls(x),l,r,y); 100 if(r> mid)add(rs(x),l,r,y); 101 sum(x)=sum(ls(x))+sum(rs(x)); 102 } 103 LL ask(rec int x,rec int l,rec int r) 104 { 105 if(l>r)return 0; 106 down(x); 107 if(l(x)>=l&&r(x)<=r)return sum(x); 108 int mid=(l(x)+r(x))>>1;LL ans=0; 109 if(l<=mid)ans+=ask(ls(x),l,r); 110 if(r> mid)ans+=ask(rs(x),l,r); 111 return ans; 112 } 113 }T; 114 inline int read(); 115 inline void add(rec int u,rec int v); 116 signed main() 117 { 118 // freopen("S1_1.in","r",stdin); 119 // freopen("in.txt","r",stdin); 120 // freopen("1.out","w",stdout); 121 122 n=read(),q=read();int tu,tv; 123 for(re int i=1;i<=n;i++)w[i]=read(); 124 for(re int i=1;i<n;i++)tu=read(),tv=read(),add(tu,tv),add(tv,tu); 125 re int root=1; 126 dep[1]=1;dfs1(1),dfs2(1,1);T.build(1,1,n); 127 re int opt,a,b,c; 128 for(re int i=1;i<=q;i++) 129 { 130 opt=read(); 131 if(opt==1)a=read(),root=a; 132 if(opt==2) 133 { 134 a=read(),b=read(),c=read(); 135 int lca=LCA(a,b); 136 if(lca==root)T.add(1,1,n,c); 137 else if(dfn[root]<L[lca]||dfn[root]>R[lca])T.add(1,L[lca],R[lca],c); 138 else 139 { 140 int t1=LCA(a,root),t2=LCA(b,root); 141 if(dep[t1]>dep[t2])lca=t1; 142 else lca=t2; 143 if(lca==root)T.add(1,1,n,c); 144 else if(dfn[root]<L[lca]||dfn[root]>R[lca])T.add(1,L[lca],R[lca],c); 145 else 146 { 147 int te=upper_bound(inc[lca].begin(),inc[lca].end(),dfn[root])-inc[lca].begin()-1; 148 lca=inc[lca][te];lca=id[lca]; 149 T.add(1,1,L[lca]-1,c),T.add(1,R[lca]+1,n,c); 150 } 151 } 152 } 153 if(opt==3) 154 { 155 a=read(); 156 if(a==root)printf("%lld ",T.ask(1,1,n)); 157 else if(dfn[root]<L[a]||dfn[root]>R[a])printf("%lld ",T.ask(1,L[a],R[a])); 158 else 159 { 160 int te=upper_bound(inc[a].begin(),inc[a].end(),dfn[root])-inc[a].begin()-1; 161 te=inc[a][te];te=id[te]; 162 printf("%lld ",T.ask(1,1,L[te]-1)+T.ask(1,R[te]+1,n)); 163 } 164 } 165 } 166 return 0; 167 } 168 inline int read() 169 { 170 int s=0,f=1;char a=getchar(); 171 while(a<'0'||a>'9'){if(a=='-')f=-1;a=getchar();} 172 while(a>='0'&&a<='9'){s=s*10+a-'0';a=getchar();} 173 return s*f; 174 } 175 inline void add(rec int u,rec int v) 176 { 177 ++num_e; 178 u(num_e)=u; 179 v(num_e)=v; 180 n(num_e)=f(u); 181 f(u)=num_e; 182 }