XVIII.[PA2017]Banany
心血来潮想开道动态点分治的题练手，然后被折磨了一下午……
首先，套上点分树是没问题的。那么，怎样维护修改呢？
单点修改无论用什么结构维护都是非常easy的；但是边的修改就不太简单了，因为它涉及到不止一条路径。
我们设当前修改了边 \((x,y)\)。对于点分树上的点，若其在原树上的 \(x\) 一侧，显然其子树中 \(y\) 一侧的路径要变化；若其在原树上 \(y\) 一侧，则 \(x\) 一侧的路径要变化。
考虑所有分治块横跨 \((x,y)\) 边的点，发现其仅有可能是 \(x,y\) 之一的祖先。于是我们只需处理 \(x,y\) 祖先的并集。
某侧的路径要变化，在原树上是子树。于是我们便知道了应该用何种结构维护修改：套在原树dfs序上的线段树。这样子，\(x\) 侧点就修改 \(y\) 侧路径（在原树dfs序上是一段区间），\(y\) 侧点就修改 \(x\) 侧路径（也是一段区间），便能做到单次修改 \(O(\log n)\)。
但是我们似乎忘记还要挖掉子节点的分治树的答案。但是仔细一想，如果算了子节点的答案，就等价于路径是到了当前节点再折返，答案一定更劣（因为边权为正），所以不用考虑挖不挖子节点的答案。
于是移动就直接用线段树的答案和两点间距离拼出来即可。注意这里两点间距离应是实际距离，会随着边权修改而变化，因此要专门开一棵BIT维护！
细节大概就这么多。时间复杂度 \(O(n\log^2n)\)。线段树不要写动态开点，直接用 vector 维护即可。
代码：
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define rg register
typedef long long ll;
int n,m;
ll a[100100];
namespace CDT{
struct dat{
ll val;int id;
dat(){val=0xc0c0c0c0c0c0c0c0,id=0;}
dat(ll V,int I){val=V,id=I;}
friend bool operator<(const dat&u,const dat&v){return u.val!=v.val?u.val<v.val:u.id>v.id;}
void operator+=(const ll&v){val+=v;}
friend dat operator-(const dat&u,const ll&v){return dat(u.val-v,u.id);}
};
struct SegTree{dat mx;ll tag;void operator+=(const ll&v){mx+=v,tag+=v;}};
struct ST:vector<SegTree>{
#define lson x<<1|1
#define rson (x+1)<<1
#define mid ((l+r)>>1)
void pushup(int x){(*this)[x].mx=max((*this)[lson].mx,(*this)[rson].mx);}
void pushdown(int x){ll&v=(*this)[x].tag;(*this)[lson]+=v,(*this)[rson]+=v,v=0;}
void modify(int x,int l,int r,int L,int R,ll val){
if(l>R||r<L)return;
if(L<=l&&r<=R){(*this)[x]+=val;return;}
pushdown(x),modify(lson,l,mid,L,R,val),modify(rson,mid+1,r,L,R,val),pushup(x);
}
void modify(int x,int l,int r,int P,dat val){
if(l>P||r<P)return;
if(l==r){(*this)[x].mx=val;return;}
pushdown(x),modify(lson,l,mid,P,val),modify(rson,mid+1,r,P,val),pushup(x);
}
dat query(int x,int l,int r,int ban){
if((*this)[x].mx.id!=ban)return (*this)[x].mx;
if(l==r)return dat();
pushdown(x);return max(query(lson,l,mid,ban),query(rson,mid+1,r,ban));
}
int build(int x,int l,int r){if(l==r)return x;return max(build(lson,l,mid),build(rson,mid+1,r));}
void iterate(int x,int l,int r){printf("%d:[%d,%d]:%lld,%d\n",x,l,r,(*this)[x].mx.val,(*this)[x].mx.id);if(l!=r)pushdown(x),iterate(lson,l,mid),iterate(rson,mid+1,r);}
}seg[100100];
int RT;
vector<int>v[100100];
int fa[100100];
}
namespace TRE{
int head[100100],cnt,sz[100100],msz[100100],RT,SZ;
struct node{int to,next;ll val;}edge[201000];
il void ae(rg int u,rg int v,rg ll w){
edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=w,head[v]=cnt++;
}
bool vis[100100];
il void getroot(rg int x,rg int fa){
sz[x]=1,msz[x]=0;
for(rg int i=head[x],y;i!=-1;i=edge[i].next)if((y=edge[i].to)!=fa&&!vis[y])getroot(y,x),sz[x]+=sz[y],msz[x]=max(msz[x],sz[y]);
msz[x]=max(msz[x],SZ-sz[x]);
if(msz[x]<msz[RT])RT=x;
}
il void getsz(rg int x,rg int fa){sz[x]=1;for(rg int i=head[x],y;i!=-1;i=edge[i].next)if((y=edge[i].to)!=fa&&!vis[y])getsz(y,x),sz[x]+=sz[y];}
il void solve(rg int x){
getsz(x,0),vis[x]=true;
for(rg int i=head[x],y;i!=-1;i=edge[i].next)if(!vis[y=edge[i].to])RT=0,SZ=sz[y],getroot(y,0),CDT::fa[RT]=x,solve(RT);
}
int dep[100100],st[200100][20],tot,LG[200100],fir[100100],dfn[100100],nfd;
ll dis[100100],val[100100];
il void dfs(int x,int fa){
st[++tot][0]=x,fir[x]=tot,dfn[x]=++nfd,sz[x]=1;
for(rg int i=head[x],y;i!=-1;i=edge[i].next)if((y=edge[i].to)!=fa)dis[y]=dis[x]+(val[y]=edge[i].val),dep[y]=dep[x]+1,dfs(y,x),st[++tot][0]=x,sz[x]+=sz[y];
}
il int MIN(rg int x,rg int y){return dep[x]<dep[y]?x:y;}
il int LCA(rg int x,rg int y){x=fir[x],y=fir[y];if(x>y)swap(x,y);int k=LG[y-x+1];return MIN(st[x][k],st[y-(1<<k)+1][k]);}
il ll DIS(rg int x,rg int y){return dis[x]+dis[y]-2*dis[LCA(x,y)];}
il void init(){
memset(head,-1,sizeof(head));for(rg int i=1;i<n;i++){int x,y;ll z;scanf("%d%d%lld",&x,&y,&z),ae(x,y,z);}
msz[RT=0]=SZ=n,getroot(1,0),solve(CDT::RT=RT);
dfs(1,0);for(rg int i=2;i<=tot;i++)LG[i]=LG[i>>1]+1;
for(rg int j=1;j<=LG[tot];j++)for(rg int i=1;i+(1<<j)-1<=tot;i++)st[i][j]=MIN(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
ll t[100100];
void ADD(int x,ll y){while(x<=n)t[x]+=y,x+=x&-x;}
ll SUM(int x){ll ret=0;while(x)ret+=t[x],x-=x&-x;return ret;}
ll DS(int x){return dis[x]+SUM(dfn[x]);}
ll D(int x,int y){return DS(x)+DS(y)-2*DS(LCA(x,y));}
}
using TRE::DIS;
using TRE::dfn;
using TRE::sz;
using TRE::D;
namespace CDT{
#define all(x) x.begin(),x.end()
int P=1;
void init(){
for(int i=1;i<=n;i++)for(int j=i;j;j=fa[j])v[j].push_back(dfn[i]);
// for(int i=1;i<=n;i++){for(auto j:v[i])printf("%d ",j);puts("");}
for(int i=1;i<=n;i++)sort(all(v[i])),seg[i].resize(seg[i].build(0,0,v[i].size()-1)+1);
// for(int i=1;i<=n;i++)printf("%d %d\n",seg[i].size(),v[i].size()),seg[i].iterate(0,0,v[i].size()-1),puts("");
for(int i=1;i<=n;i++)for(int j=i;j;j=fa[j])seg[j].modify(0,0,v[j].size()-1,lower_bound(all(v[j]),dfn[i])-v[j].begin(),dat(a[i]-DIS(i,j),i));
}
void modifypoint(int x,ll val){val-=a[x],a[x]+=val;for(int y=x,p;y;y=fa[y])p=lower_bound(all(v[y]),dfn[x])-v[y].begin(),seg[y].modify(0,0,v[y].size()-1,p,p,val);}
bool sp[100100];
void IN(int z,int x,ll val){
seg[z].modify(0,0,v[z].size()-1,0,(lower_bound(all(v[z]),dfn[x])-v[z].begin())-1,-val);
seg[z].modify(0,0,v[z].size()-1,upper_bound(all(v[z]),dfn[x]+sz[x]-1)-v[z].begin(),v[z].size()-1,-val);
}
void OUT(int z,int x,ll val){
seg[z].modify(0,0,v[z].size()-1,lower_bound(all(v[z]),dfn[x])-v[z].begin(),(upper_bound(all(v[z]),dfn[x]+sz[x]-1)-v[z].begin())-1,-val);
}
void modifyedge(int x,int y,ll val){
if(TRE::dep[x]<TRE::dep[y])swap(x,y);
// printf("[%d,%d,%d]\n",x,TRE::val[x],val);
val-=TRE::val[x],TRE::val[x]+=val;
TRE::ADD(dfn[x],val),TRE::ADD(dfn[x]+sz[x],-val);
for(int z=x;z;sp[z]=true,z=fa[z])if(dfn[z]>=dfn[x]+sz[x]||dfn[z]<dfn[x])OUT(z,x,val);else IN(z,x,val);
for(int z=y;z;z=fa[z]){
if(sp[z])continue;
if(dfn[z]>=dfn[x]+sz[x]||dfn[z]<dfn[x])OUT(z,x,val);else IN(z,x,val);
}
for(int z=x;z;sp[z]=false,z=fa[z]);
}
void query(){dat mx;for(int z=P;z;z=fa[z])mx=max(mx,seg[z].query(0,0,v[z].size()-1,P)-D(P,z));P=mx.id;}
}
int main(){
scanf("%d%d",&n,&m);
for(rg int i=1;i<=n;i++)scanf("%lld",&a[i]);
TRE::init(),CDT::init();
for(int i=1,tp;i<=m;i++){
int x,y;ll z;scanf("%d",&tp);
if(tp==1)scanf("%d%lld",&x,&z),CDT::modifypoint(x,z);else scanf("%d%d%lld",&x,&y,&z),CDT::modifyedge(x,y,z);
// for(int j=1;j<=n;j++)CDT::seg[j].iterate(0,0,CDT::v[j].size()-1),puts("");
CDT::query();printf("%d ",CDT::P);
}
return 0;
}