题意
给一棵树，带点权（可为负），单点修改，求直径，求过某一点的直径 \((n<=100000)\)
思路
发现强制过某一点，可以转化为单点改成正无穷，求直径
于是就只用考虑单点修改求直径
考虑点分树，在每个重心维护到他的最长链，和不同子树中的次长链，全部答案取个max即可（但是被卡常）
code
#pragma GCC optimize("Ofast", "inline", "-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 100005
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int rd() {
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
return x*f;
}
int n,m,k,cnt;
int a[N],h[N];
const int inf=1e15;
struct AB{
int a,b,n;
}d[N*2];
void cun(int x,int y){
d[++k]={x,y,h[x]},h[x]=k;
}
struct DUI{
priority_queue<int> q1,q2;
void ins(int x){q1.push(x);}
void del(int x){q2.push(x);}
void upd(){
while(!q1.empty()&&!q2.empty()&&q1.top()==q2.top()) q1.pop(),q2.pop();
}
int top(){
upd();
return q1.top();
}
}ans;
struct TREE{
int mx1,mx2,col1;
TREE(){col1=0,mx1=mx2=-inf;}
};
namespace T2{
int tot;
int rt[N],fu[N],sz[N],mxs[N],ct[N],cl[19][N],szz[19][N],tt[19],idd[19][N],de[N],tag[N*4*18];
TREE c[N*4*20];
void xin(int &p,int l1,int l2){
if(l1+l2>p) p=l1+l2;
}
TREE merge(TREE A,TREE B){
TREE C;
C.mx1=C.mx2=-inf,C.col1=0;
if(A.mx1>B.mx1){
C.mx1=A.mx1,C.col1=A.col1;
if(A.mx2>=B.mx1) C.mx2=A.mx2;
else if(B.col1!=C.col1||!B.col1||!C.col1) C.mx2=B.mx1;
else C.mx2=max(A.mx2,B.mx2);
}
else{
C.mx1=B.mx1,C.col1=B.col1;
if(B.mx2>=A.mx1) C.mx2=B.mx2;
else if(A.col1!=C.col1||!A.col1||!C.col1) C.mx2=A.mx1;
else C.mx2=max(B.mx2,A.mx2);
}
return C;
}
void gai(int p,int l,int r,int x,int y,int col,int sum){
if(l==r){
c[p+sum].col1=col,c[p+sum].mx1=y;
return ;
}
int mid=(l+r)>>1;
if(x<=mid) gai(p*2,l,mid,x,y,col,sum);
else gai(p*2+1,mid+1,r,x,y,col,sum);
c[p+sum]=merge(c[p*2+sum],c[p*2+1+sum]);
}
void jia(int p,int z){
if(!p) return ;
c[p].mx1=c[p].mx1+z;
if(c[p].mx2!=-inf) c[p].mx2=c[p].mx2+z;
tag[p]+=z;
}
void down(int p,int sum){
if(!tag[p+sum]) return ;
int ls=p*2+sum,rs=p*2+1+sum;
jia(ls,tag[p+sum]),jia(rs,tag[p+sum]),tag[p+sum]=0;
}
void jian(int p,int l,int r,int x,int y,int z,int sum){
if(x<=l&&r<=y){
jia(p+sum,z);
return ;
}
down(p,sum);
int mid=(l+r)>>1;
if(x<=mid) jian(p*2,l,mid,x,y,z,sum);
if(mid<y) jian(p*2+1,mid+1,r,x,y,z,sum);
c[p+sum]=merge(c[p*2+sum],c[p*2+1+sum]);
}
TREE gt_ans(int p,int l,int r,int x,int y,int sum){
if(x<=l&&r<=y) return c[p+sum];
int mid=(l+r)>>1;
if(x<=mid&&mid<y) return merge(gt_ans(p*2,l,mid,x,y,sum),gt_ans(p*2+1,mid+1,r,x,y,sum));
else if(x<=mid) return gt_ans(p*2,l,mid,x,y,sum);
else return gt_ans(p*2+1,mid+1,r,x,y,sum);
}
void dfs(int x,int fa,int f,int col,int dd,int dis){
cl[dd][x]=col,idd[dd][x]=++tt[dd],szz[dd][x]=1;
gai(1,1,n,tt[dd],dis,col,rt[dd]);
for(int i=h[x];i;i=d[i].n){
int y=d[i].b;
if(ct[y]||y==fa) continue;
dfs(y,x,f,col,dd,dis+a[y]);szz[dd][x]+=szz[dd][y];
}
}
void gt_sz(int x,int fa){
sz[x]=1,mxs[x]=0;
for(int i=h[x];i;i=d[i].n){
int y=d[i].b;
if(y==fa||ct[y]) continue;
gt_sz(y,x);sz[x]+=sz[y],mxs[x]=max(mxs[x],sz[y]);
}
}
int gt_rt(int x,int fa,int sum){
int q=x;
mxs[x]=max(mxs[x],sum-sz[x]);
for(int i=h[x];i;i=d[i].n){
int y=d[i].b;
if(y==fa||ct[y]) continue;
int p=gt_rt(y,x,sum);
if(mxs[p]<mxs[q]) q=p;
}
return q;
}
inline int anns(int x){
if(szz[de[x]][x]==1) return 0;
TREE A=gt_ans(1,1,n,idd[de[x]][x]+1,idd[de[x]][x]+szz[de[x]][x]-1,rt[de[x]]);
return max(0ll,A.mx1)+max(0ll,A.mx2);
}
void bui(int x,int dd){
ct[x]=1,de[x]=dd,idd[dd][x]=++tt[dd],szz[dd][x]=1;
for(int i=h[x];i;i=d[i].n) {
if(ct[d[i].b]) continue;
dfs(d[i].b,0,x,d[i].b,dd,a[d[i].b]),szz[dd][x]+=szz[dd][d[i].b];
}
ans.ins(anns(x)+a[x]);
for(int i=h[x];i;i=d[i].n){
int y=d[i].b;
if(ct[y]) continue;
gt_sz(y,x);
int rt=gt_rt(y,0,sz[y]);
fu[rt]=x;bui(rt,dd+1);
}
}
inline void add(int x,int y){
for(int i=fu[x];i;i=fu[i]){
ans.del(anns(i)+a[i]);
jian(1,1,n,idd[de[i]][x],idd[de[i]][x]+szz[de[i]][x]-1,y,rt[de[i]]);
ans.ins(anns(i)+a[i]);
}
}
void build(){
gt_sz(1,0);
int rrt=gt_rt(1,0,sz[1]);
for(int i=1;i<=18;i++) rt[i]=(i-1)*n*4;
bui(rrt,1);
}
}
inline void upd(int x,int y){
ans.del(T2::anns(x)+a[x]);
T2::add(x,y-a[x]);a[x]=y;
ans.ins(T2::anns(x)+a[x]);
}
signed main(){
freopen("taffy.in","r",stdin);
freopen("taffy.out","w",stdout);
scanf("%lld%lld",&n,&m);
for(int i=1,x,y;i<n;i++){
x=rd(),y=rd();
cun(x,y),cun(y,x);
}
for(int i=1;i<=n;i++) a[i]=rd();
T2::build();
while(m--){
int op,x,y;
op=rd();
if(op==1) printf("%lld\n",ans.top());
else if(op==2){
x=rd();upd(x,a[x]+inf);
printf("%lld\n",ans.top()-inf);
upd(x,a[x]-inf);
}
else{
x=rd(),y=rd();
upd(x,y);
}
}
return 0;
}