RT
样例过了
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN=5e5+5,MAXS=3e7+5,INF=1e15;
ll n,m;
ll op,x,y;
ll val[MAXN];
struct edge{
ll u,v,nxt;
}e[MAXN],tree[MAXN];
ll head[MAXN],head_tree[MAXN],edge_num,edge_num_tree;
void add_edge(ll From,ll To){
e[++edge_num]=(edge){From,To,head[From]};
head[From]=edge_num;
return;
}
void add_tree(ll From,ll To){
if(To<1||From<1)return;
tree[++edge_num_tree]=(edge){From,To,head_tree[From]};
head_tree[From]=edge_num_tree;
return;
}
ll deep[MAXN],fa[MAXN][35];
void pre_dis(ll now,ll father){
deep[now]=deep[father]+1;
fa[now][0]=father;
for(int i=1;i<=30;i++)fa[now][i]=fa[fa[now][i-1]][i-1];
for(int i=head[now];i;i=e[i].nxt){
if(e[i].v==father)continue;
pre_dis(e[i].v,now);
}
return;
}
ll lca(ll X,ll Y){
if(deep[X]<deep[Y])swap(X,Y);
for(int i=30;i>=0&&deep[X]>deep[Y];i--)if(deep[fa[X][i]]>=deep[Y])X=fa[X][i];
if(X==Y)return X;
for(int i=30;i>=0;i--)if(fa[X][i]!=fa[Y][i])X=fa[X][i],Y=fa[Y][i];
return fa[X][0];
}
ll dis(ll X,ll Y){
ll Z=lca(X,Y);
return deep[X]+deep[Y]-(deep[Z]<<1);
}
ll sum,sz[MAXN],rt,max_sz[MAXN],fa_on_tree[MAXN];
bool vis[MAXN];
void calc_sz(ll now,ll father){
sz[now]=1;
max_sz[now]=0;
for(int i=head[now];i;i=e[i].nxt){
if(e[i].v==father||vis[e[i].v])continue;
calc_sz(e[i].v,now);
sz[now]+=sz[e[i].v];
max_sz[now]=max(max_sz[now],sz[e[i].v]);
}
max_sz[now]=max(max_sz[now],sum-sz[now]);
if(max_sz[now]<max_sz[rt])rt=now;
return;
}
void build_tree(ll now,ll father){
add_tree(now,father);
add_tree(father,now);
fa_on_tree[now]=father;
vis[now]=1;
for(int i=head[now];i;i=e[i].nxt){
if(e[i].v==father||vis[e[i].v])continue;
sum=sz[e[i].v];
rt=0;
max_sz[0]=INF;
calc_sz(e[i].v,now);
calc_sz(rt,-1);
build_tree(rt,now);
}
return;
}
struct sgm_t{
ll sum[MAXS],lson[MAXS],rson[MAXS],rt[MAXN];
ll cnt;
void update(ll &id,ll L,ll R,ll k,ll delta){
if(k<L||k>R||L>R)return;
if(id==0)id=++cnt;
sum[id]+=delta;
if(L==R)return;
ll mid=(L+R)>>1;
if(k<=mid)update(lson[id],L,mid,k,delta);
else update(rson[id],mid+1,R,k,delta);
return;
}
ll query(ll id,ll L,ll R,ll QL,ll QR){
if(QL>QR)return 0;
if(L>QR||R<QL||L>R||!id)return 0;
if(QL<=L&&R<=QR)return sum[id];
ll mid=(L+R)>>1;
return query(lson[id],L,mid,QL,QR)+query(rson[id],mid+1,R,QL,QR);
}
}S,fa_S;
void change(ll X,ll Y){
S.update(S.rt[X],0,n,0,Y-val[X]);
ll lst=X,now=fa_on_tree[X];
while(now>=1){
S.update(S.rt[now],0,n,dis(X,now),Y-val[X]);
fa_S.update(fa_S.rt[lst],0,n,dis(X,now),Y-val[X]);
lst=now;
now=fa_on_tree[now];
}
val[X]=Y;
return;
}
ll Q(ll X,ll Y){
ll ans=0;
ans+=S.query(S.rt[X],0,n,0,Y);
ll lst=X,now=fa_on_tree[X];
while(now>=1){
ans+=S.query(S.rt[now],0,n,0,Y-dis(X,now));
ans-=fa_S.query(fa_S.rt[lst],0,n,0,Y-dis(X,now));
lst=now;
now=fa_on_tree[now];
}
return ans;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>val[i];
ll qwq[MAXN];
for(int i=1;i<=n;i++)qwq[i]=val[i],val[i]=0;
for(int i=1;i<n;i++){
cin>>x>>y;
add_edge(x,y);
add_edge(y,x);
}
sum=n;
rt=0;
max_sz[0]=INF;
calc_sz(1,-1);
calc_sz(rt,-1);
pre_dis(rt,0);
ll tmp_rt=rt;
build_tree(rt,-1);
// for(int i=1;i<=edge_num_tree;i++)cout<<tree[i].u<<" "<<tree[i].v<<'\n';
rt=tmp_rt;
for(int i=1;i<=n;i++)change(i,qwq[i]);
for(int i=1;i<=m;i++){
cin>>op;
if(op==1){
cin>>x>>y;
change(x,y);
}
else{
cin>>x>>y;
cout<<Q(x,y)<<'\n';
}
}
return 0;
}