我们先以 \(1\) 为根进行剖一遍。
对于链上的搞事，换根与不换根本质上是一样的。所以我们在这里只讨论对于子树的搞事。
我们设当前的根为 \(rt\)，要对以 \(u\) 为根的子树搞事。
三种情况：
第一种：\(u=rt\)。这个应该不用说了吧。。
第二种：\(\operatorname{LCA}(u,rt)\ne u\)（这里 LCA 是以 \(1\) 为根计算的）。可以细分为以下三种情况：
然后我们发现此时以 \(rt\) 为根和以 \(1\) 为根是没有区别的！
第三种（也是最复杂的一种）：\(\operatorname{LCA}(u,rt)=u\)。此时 \(u\) 在 \(1\leftrightarrow rt\) 的路径上：
此时，我们要搞事的部分就是整棵树除掉以 \(1\) 为根时 \(v\) 的子树。我们知道，一棵树的子树在 dfn 序上是连续的一段，所以我们只需对 \([1,dfn_v)\) 和 \((dfn_v+siz_v-1,n]\) 搞事。注意，这两个区间可能是空集，所以我们要判一下，如果是空集就不搞事了。
另外还有一个问题：如何找到这个 \(v\)？事实上将 \(rt\) 向上跳 \(dep_{rt}-dep_u-1\) 步即为所求，用树上倍增实现即可。
习题：loj139。
参考代码：
#include<cstdio>
#include<algorithm>
typedef long long ll;
const int N=1e5;
struct Edge{int to,nxt;}e[N*2+10];int head[N+10],tote=1;
inline void addEdge(int u,int v){e[++tote].to=v;e[tote].nxt=head[u];head[u]=tote;}
int n,m,a[N+10],rt;
int fa[N+10],siz[N+10],son[N+10],dep[N+10],dfn[N+10],rk[N+10],top[N+10],cnt;
int f[N+10][20];
struct SegTree{
struct Node{
ll v,atag;
Node(ll _v=0,ll _atag=-1):v(_v),atag(_atag){}
};
Node t[N*4+10];
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
inline Node pushUp(Node L,Node R){
Node res;
res.v=L.v+R.v;
return res;
}
inline void pushAdd(int i,int l,int r,ll atag){
t[i].v+=1LL*atag*(r-l+1);
if(t[i].atag!=-1)t[i].atag+=atag;
else t[i].atag=atag;
}
inline void pushDown(int i,int l,int r){
if(t[i].atag!=-1){
int mid=(l+r)>>1;
pushAdd(ls(i),l,mid,t[i].atag);
pushAdd(rs(i),mid+1,r,t[i].atag);
t[i].atag=-1;
}
}
void build(int i,int l,int r){
if(l==r){
t[i].v=a[rk[l]];
return;
}
int mid=(l+r)>>1;
build(ls(i),l,mid);
build(rs(i),mid+1,r);
t[i]=pushUp(t[ls(i)],t[rs(i)]);
}
void modify(int i,int l,int r,int ql,int qr,int x){
if(ql<=l&&r<=qr){
pushAdd(i,l,r,x);
return;
}
int mid=(l+r)>>1;
pushDown(i,l,r);
if(ql<=mid)modify(ls(i),l,mid,ql,qr,x);
if(qr>mid) modify(rs(i),mid+1,r,ql,qr,x);
t[i]=pushUp(t[ls(i)],t[rs(i)]);
}
Node query(int i,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return t[i];
int mid=(l+r)>>1;
pushDown(i,l,r);
if(qr<=mid)return query(ls(i),l,mid,ql,qr);
if(ql>mid) return query(rs(i),mid+1,r,ql,qr);
return pushUp(query(ls(i),l,mid,ql,qr),query(rs(i),mid+1,r,ql,qr));
}
#undef ls
#undef rs
}t;
void DFS1(int u,int _fa){
fa[u]=_fa;
dep[u]=dep[_fa]+1;
siz[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==_fa)continue;
DFS1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
}
void DFS2(int u,int _fa,int _top){
dfn[u]=++cnt;
rk[cnt]=u;
top[u]=_top;
if(son[u])DFS2(son[u],u,_top);
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==_fa||v==son[u])continue;
DFS2(v,u,v);
}
}
void modify(int u,int v,int x){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])std::swap(u,v);
t.modify(1,1,n,dfn[top[u]],dfn[u],x);
u=fa[top[u]];
}
if(dep[u]>dep[v])std::swap(u,v);
t.modify(1,1,n,dfn[u],dfn[v],x);
}
SegTree::Node query(int u,int v){
SegTree::Node res;
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])std::swap(u,v);
res=t.pushUp(res,t.query(1,1,n,dfn[top[u]],dfn[u]));
u=fa[top[u]];
}
if(dep[u]>dep[v])std::swap(u,v);
res=t.pushUp(res,t.query(1,1,n,dfn[u],dfn[v]));
return res;
}
inline int get(int u){
int v=rt,k=dep[rt]-dep[u]-1;
for(int i=17;~i;i--)
if(k-(1<<i)>=0)v=f[v][i],k-=(1<<i);
return v;
}
inline int LCA(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])std::swap(u,v);
u=fa[top[u]];
}
if(dep[u]>dep[v])std::swap(u,v);
return u;
}
void subtreeModify(int u,int x){
if(u==rt)t.modify(1,1,n,1,n,x);
else if(LCA(u,rt)!=u)t.modify(1,1,n,dfn[u],dfn[u]+siz[u]-1,x);
else{
int v=get(u);
if(dfn[v]-1>=1)t.modify(1,1,n,1,dfn[v]-1,x);
if(dfn[v]+siz[v]<=n)t.modify(1,1,n,dfn[v]+siz[v],n,x);
}
}
SegTree::Node subtreeQuery(int u){
if(u==rt)return t.query(1,1,n,1,n);
else if(LCA(u,rt)!=u)return t.query(1,1,n,dfn[u],dfn[u]+siz[u]-1);
else{
int v=get(u);
SegTree::Node res;;
if(dfn[v]-1>=1)res=t.pushUp(res,t.query(1,1,n,1,dfn[v]-1));
if(dfn[v]+siz[v]<=n)res=t.pushUp(res,t.query(1,1,n,dfn[v]+siz[v],n));
return res;
}
}
int main(){
scanf("%d",&n);
rt=1;
for(int i=1;i<=n;i++)
scanf("%d",a+i);
for(int i=2;i<=n;i++){
int x;scanf("%d",&x);
addEdge(i,x),addEdge(x,i);
}
DFS1(1,0),DFS2(1,0,1),t.build(1,1,n);
for(int i=1;i<=n;i++)
f[i][0]=fa[i];
for(int j=1;j<=17;j++)
for(int i=1;i<=n;i++)
f[i][j]=f[f[i][j-1]][j-1];
scanf("%d",&m);
while(m--){
int opt,x,y,z;
scanf("%d%d",&opt,&x);
if(opt==1)rt=x;
if(opt==2)scanf("%d%d",&y,&z),modify(x,y,z);
if(opt==3)scanf("%d",&z),subtreeModify(x,z);
if(opt==4)scanf("%d",&y),printf("%lld\n",query(x,y).v);
if(opt==5)printf("%lld\n",subtreeQuery(x).v);
}
return 0;
}