仔细考虑这道题，我们可以将问题转化为「修改」和「换根」两个操作。
对于修改操作，我们知道，每个点的权值对且仅对它到根节点上的这一条链上的每个点的答案产生贡献。
我们不妨令以1为根的情况下的每个点的修改前子树权值和为\(a_{i}\)，修改对权值的改变为\(dlt\)，那么可以计算得：
$$ans’=\sum(a_{i}+dlt)^2=\sum a_{i}^2+2dlt\times a_{i}+dlt^2\times len$$
故而，我们只需要用树链剖分套线段树维护树上区间平方和即可。
接下来我们考虑换根操作。
我们假设根从1换到了\(x\)，那么子树权值大小会发生改变的仅有这条路径经过的点。我们不妨令换根后它们的子树权值和为\(b_{i}\)，并有1~x为这条路径构成的序列，则我们发现答案会做出如下变动：
$$ans’=ans-\sum_{i=x}^1 a_{i}^2+\sum_{i=x}^1 b_{i}^2$$
我们发现，路径上的相邻点的子树的并集构成了整棵树。这也就意味着：
$$a_{i}+b_{i+1}=a_{0}=b_{x}$$
于是我们可以依此得到：
$$ans’=ans-\sum_{i=x}^1 a_{i}^2+b_x^2+\sum_{i=x-1}^1 (a_{0}-a_{i+1})^2$$
$$ans’=ans-\sum_{i=x}^2 a_{i}^2+(len-1)\times a_{0}^2-2a_{0}\times\sum_{i=x-1}^1 a_{i+1}+\sum_{i=x}^2a_{i}^2$$
$$ans’=(len-1)a_0^2-2a_{0}\sum_{i=x}^2a_{i}$$
同样也可以用树链剖分套线段树维护树上区间和与区间平方和。
注意：树剖不要写挂，下传给重儿子的链顶应该是本节点的链顶。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define Fv(i,X) for(int i=h[X];i;i=e[i].nxt)
typedef long long ll;
inline char rdc() {
static char buf[10000000], *p = buf, *end = buf;
if (p == end) end = buf + fread(p = buf, sizeof(char), 10000000, stdin);
return *(p++);
}
inline int rd(){
int RT=0,c,f=1;
while(!isdigit(c=rdc())){if(c=='-'){f=-1;}}
do{RT=RT*10+c-'0';}while(isdigit(c=rdc()));
return RT*f;
}
struct ee{
int v;
int nxt;
}e[400005];
int h[200005],et=0;
inline void Eadd(int U,int V){
e[++et]=(ee){V,h[U]};
h[U]=et;
}
inline void add(int U,int V){
Eadd(U,V);
Eadd(V,U);
}
int n,q;
ll val[200005],sm[200005];
int fa[200005],dep[200005],tp[200005],sn[200005],sz[200005];
int dfn[200005],loc[200005],cnt=0;
inline void dfs0(int X,int FA){
dep[X]=dep[FA]+1;
fa[X]=FA;
sz[X]=1;
sm[X]=val[X];
Fv(i,X){
if(e[i].v==FA){
continue;
}
dfs0(e[i].v,X);
sz[X]+=sz[e[i].v];
if(sz[e[i].v]>sz[sn[X]]){
sn[X]=e[i].v;
}
sm[X]+=sm[e[i].v];
}
}
inline void dfs1(int X,int TP){
loc[dfn[X]=++cnt]=X;
tp[X]=TP;
if(sn[X]){
dfs1(sn[X],TP);
//这里下传的应该是TP而非X...
//树剖写挂了，我SB
}
Fv(i,X){
if(e[i].v==fa[X]||e[i].v==sn[X]){
continue;
}
dfs1(e[i].v,e[i].v);
}
}
#define MID ((L+R)>>1)
#define LS (X<<1)
#define RS (X<<1|1)
#define LEN (R-L+1)
#define LLEN (MID-L+1)
#define RLEN (R-MID)
struct data{
ll sm;
ll sm2;
ll lzy;
}tr[2000005];
inline void rnw(int X,int Len,ll K){
tr[X].sm2+=(K*K*Len+tr[X].sm*K*2);
tr[X].sm+=(Len*K);
tr[X].lzy+=K;
}
inline void pshd(int X,int L,int R){
rnw(LS,LLEN,tr[X].lzy),rnw(RS,RLEN,tr[X].lzy);
tr[X].lzy=0;
}
inline void updt(int X){
tr[X].sm=tr[LS].sm+tr[RS].sm;
tr[X].sm2=tr[LS].sm2+tr[RS].sm2;
}
inline void chg(int X,int L,int R,int A,int B,int V){
if(L>=A&&R<=B){
rnw(X,LEN,V);
return;
}
pshd(X,L,R);
if(A<=MID){
chg(LS,L,MID,A,B,V);
}
if(B>MID){
chg(RS,MID+1,R,A,B,V);
}
updt(X);
}
inline ll qrySm(int X,int L,int R,int A,int B){
if(L>=A&&R<=B){
return tr[X].sm;
}
if(L>B||R<A||B<A){
return 0;
}
pshd(X,L,R);
return qrySm(LS,L,MID,A,B)+qrySm(RS,MID+1,R,A,B);
}
inline ll qrySm2(int X,int L,int R,int A,int B){
if(L>=A&&R<=B){
return tr[X].sm2;
}
if(L>B||R<A||B<A){
return 0;
}
pshd(X,L,R);
return qrySm2(LS,L,MID,A,B)+qrySm2(RS,MID+1,R,A,B);
}
inline void build(int X,int L,int R){
if(L==R){
tr[X].sm=sm[loc[L]];
tr[X].sm2=tr[X].sm*tr[X].sm;
return;
}
build(LS,L,MID);build(RS,MID+1,R);
updt(X);
}
void init(){
n=rd(),q=rd();
int u,v;
for(int i=1;i<n;++i){
u=rd(),v=rd();
add(u,v);
}
for(int i=1;i<=n;++i){
val[i]=rd();
}
dfs0(1,0);
dfs1(1,1);
build(1,1,n);
int op,x,y;
ll ans,a0=sm[1],sma,len;
for(int i=1;i<=q;++i){
op=rd();
if(op==1){
x=rd(),y=rd();
y-=val[x];
val[x]+=y;
a0+=y;
while(x){
chg(1,1,n,dfn[tp[x]],dfn[x],y);
x=fa[tp[x]];
}
}else{
x=rd();
len=sma=ans=0;
ans=qrySm2(1,1,n,1,n);
while(tp[x]!=tp[1]){
len+=dfn[x]-dfn[tp[x]]+1;
sma+=qrySm(1,1,n,dfn[tp[x]],dfn[x]);
x=fa[tp[x]];
}
len+=dfn[x]-dfn[1];
sma+=qrySm(1,1,n,dfn[1]+1,dfn[x]);
printf("%lld\n",ans+a0*(len*a0-2*sma));
}
}
}
int main(){
init();
return 0;
}
