$$是夜萧索漏星光，一秋叶打漫天霜。钟响，卷地西风扫鸿芒。$$
$$求索那堪路漫长，重心剖树早相忘。清唱，时空阻限又何妨？$$
PA-2017 Banany
考虑点分树。先把点分树建出来再考虑更多的事情。
对每个分治子树，维护分治子树内所有点到当前分治重心的距离加价值的最大值。考虑使用数据结构进行维护。这里我们选用动态开点线段树，按照原树上的 \(dfn\) 序建树。
修改：在潺潺的雨雾里筛出虹
那么，对于修改点权的操作就比较方便，将 \(val_i\) 修改为 \(z\) 只需要对于 \(x\) 在分治树上的所有父亲进行单点修改。
考虑如何进行修改边权。我们发现在修改 \((x,y)\) 边权为 \(z\) 的过程中，有如下的性质：
- 在分治树上，\(x,y\) 中的一个是另一个的祖先
这个很好证明，考虑第一个包含 \((x,y)\) 的分治子树，必然是 \(x\) 或者 \(y\) 作为分治重心。
那么，我们就选取在分治树上的祖先作为 \(y\)，另一个作为 \(x\)。
然后考虑什么会改变，如果一个分治子树包含 \((x,y)\) 这条边，那么如果我们将子树在原树上按照这条边分成两部分，分治重心到另一部分的所有点的距离会增加 \(z-last_{x,y}\)。
那么我们考虑如何进行操作。我们发现，我们可以直接把整棵树用 \((x,y)\) 分成两部分，设在原树以 \(1\) 为根开始 \(dfs\) 的情况下，\(x\) 是 \(y\) 的儿子，一部分是区间 \([dfn_x,dfn_x+sz_x-1]\)，另一部分是 \([1,dfn_x-1]\cup[dfn_x+sz_x,n]\)。我们可以直接在当前根上把另一部分整体加 \(z-last_{x,y}\)。在 \(modify\) 的过程中不增加新节点，不属于当前分治子树的部分虽然加了但是会被自动忽略。
这样，我们就需要维护动态开点线段树的区间加。从 \(x\) 开始找到分治树的所有父亲，用 \(dfn\) 序判断当前的 \(cur\) 在 \(x\) 那一半还是 \(y\) 那一半上，然后分类讨论进行修改。
查询：心灵深处的誓约
最后考虑如何查询。假设我们处在 \(x\)，那么我们可以跳 \(x\) 在分治树的父亲，假设它是 \(cur\)。接着在 \(cur\) 的线段树上查找离 \(cur\) 权值最大的点。将权值加上 \(x\) 到 \(cur\) 的路径长度，得到它到 \(x\) 的距离。在一般的点分树上，这样做是需要先排除掉 \(cur\) 分向 \(x\) 的子树的点。但是现在边权造成的贡献是负的，也就是应当尽量少走边，那么可能被 \(cur\) 扫到的不合法的点一定可以从 \(x\) 的更低的祖先用更少的花费走到，所以不需要考虑。
但是这样还是存在问题，我们得到的最优解可能是当前点。为了维护这个问题，我们需要在线段树上维护一下次大值。
不过，还有一个问题，就是如何计算“\(x\) 到 \(cur\) 的路径长度。我们首先的想法是通过 \(lca\) 和树上倍增来计算。
参考如下代码
namespace Distance{
int Fa[100005][21],Dep[100005];ll F[100005][21];
int Dfn[100005],Ti,Sz[100005];
inline void build_distance(int x,int p,ll pval){
Fa[x][0]=p,F[x][0]=pval,Dep[x]=Dep[p]+1,Dfn[x]=++Ti,Sz[x]=1;
rep(i,1,20)Fa[x][i]=Fa[Fa[x][i-1]][i-1];
rep(i,1,20)F[x][i]=F[x][i-1]+F[Fa[x][i-1]][i-1];
for(auto e:tr[x])if(e.b!=p)build_distance(e.b,x,e.w),Sz[x]+=Sz[e.b];
}
inline int lca(int x,int y){
if(Dep[x]<Dep[y])swap(x,y);
per(i,0,20)if(Dep[Fa[x][i]]>=Dep[y])x=Fa[x][i];
if(x==y)return x;
per(i,0,20)if(Fa[x][i]!=Fa[y][i])x=Fa[x][i],y=Fa[y][i];
return Fa[x][0];
}
inline int distance(int x,int y){
ll res=0;
per(i,0,20)if(Dep[Fa[x][i]]>=Dep[y]){
res+=F[x][i];
x=Fa[x][i];
}return res;
}
inline int dis(int x,int y){
int z=lca(x,y);
return distance(x,z)+distance(y,z);
}
}using namespace Distance;
但是这样存在问题。因为我们需要的距离是可能因为边权的修改而变化的。但树上倍增显然是静态的。
对于此类问题，我们就能想到树剖，通过树剖解决树上两点动态距离。然而树剖查询动态距离本身是 \(O(\log^2n)\) 的，如果这样做，复杂度就会来到 \(O(n\log^3 n)\)。
我们发现，整个程序中只有这里一处地方需要查找距离，而且满足性质 \(cur\) 是 \(x\) 在点分树上的祖先。那么我们发现其实我们在线段树上已经存储了 \(cur\) 到 \(x\) 的距离加上 \(val_x\) 了，而 \(val_x\) 是已知的，我们就可以直接在线段树 \(cur\) 上单点查询得到距离了。
实现：来途一片血污，却笑称都是虚无
首先困扰我们的是次大值的维护，我们不仅要维护最大值，次大值，还要维护它们对应的点。
我们可以设立特殊的结构体 mxx 和 twomax，mxx 用来维护最值和它对应的位置，还要支持在值相同时小编号优先，方便的插入比较和更改数值。如果用 pair<int,int> 实现函数就略显繁琐，不如自己定义数据类型，实现 operator，保证程序简单易懂。twomax 维护两个 mxx，最大值和次大值，要支持插入 mxx，保证编号不同，以及两个 twomax 的合并。
struct twomax{
struct mxx{
int m;ll v;
mxx(int _m,ll _v){
m=_m,v=_v;
}
mxx(){
m=-1,v=-4e18;
}
void operator +=(const ll b){
v+=b;
}
bool operator >(const mxx b)const{
if(v==b.v)return m<b.m;
return v>b.v;
}
}r1,r2;
twomax(){
r1=mxx();r2=mxx();
}
twomax(int x,ll v){
r1=mxx(x,v);r2=mxx();
}
void operator +=(const mxx b){
if(b>r1){
if(r1.m!=b.m)r2=r1;
r1=b;
}
else if(b>r2&&b.m!=r1.m)r2=b;
}
void operator +=(const ll b){
r1+=b,r2+=b;
}
twomax operator +(twomax b){
twomax res=b;
res+=r1;res+=r2;
return res;
}
};
同时还利用了 C++ 对于相同的运算符或函数根据运算的数据类型进行区分的特性，调用更加方便。
然后是线段树，我们需要支持动态开点和区间加法。而区间加的过程中是不增加新点的，我们还要在 modify 之外单独实现增加新点的单点修改 build。
因为我们的 twomax 是使用运算符来操控的，好处就在于线段树可以直接用板子，非常方便。
namespace Segtree{
struct node{
int ls,rs;ll tg;twomax res;
}sg[4680005];
int cnt=0;
inline int newnode(){
int x=++cnt;
sg[x].res=twomax();sg[x].ls=0,sg[x].rs=0;
return x;
}
inline void update(int i){
sg[i].res=(sg[sg[i].ls].res+sg[sg[i].rs].res);
}
inline void pushdown(int i){
if(!i||!sg[i].tg)return;
sg[i].res+=sg[i].tg;
if(sg[i].ls)sg[sg[i].ls].tg+=sg[i].tg;
if(sg[i].rs)sg[sg[i].rs].tg+=sg[i].tg;
sg[i].tg=0;
}
inline void build(int &i,int x,int ix,ll v,int l,int r){
if(!i)i=newnode();
pushdown(i);
if(l==r){
sg[i].res=twomax(ix,v);
return;
}int mid=(l+r)>>1;
if(x<=mid)build(sg[i].ls,x,ix,v,l,mid);
else build(sg[i].rs,x,ix,v,mid+1,r);
update(i);
}
inline void modify(int i,int L,int R,ll v,int l,int r){
if(!i)return;
pushdown(i);
if(L>r||R<l)return;
if(L<=l&&r<=R){
sg[i].tg+=v;
pushdown(i);
return;
}
int mid=(l+r)>>1;
modify(sg[i].ls,L,R,v,l,mid);
modify(sg[i].rs,L,R,v,mid+1,r);
update(i);
}
inline ll qry(int i,int x,int l,int r){
pushdown(i);
if(l==r)return sg[i].res.r1.v;
int mid=(l+r)>>1;
ll res=0;
if(x<=mid){
res=qry(sg[i].ls,x,l,mid);
pushdown(sg[i].rs);
}else {
res=qry(sg[i].rs,x,mid+1,r);
pushdown(sg[i].ls);
}update(i);
return res;
}
}using namespace Segtree;
然后主程序需要实现四个函数：
-
Build_Vertex(x,y)建立 \(x\) 的点权为 \(y\)，在线段树上新建点 -
Modify_Vertex(x,y)将 \(x\) 的点权 增加 \(y\) -
Modify_Edge(x,y)将边 \((x,y)\) 的权值修改为 \(y\) -
Query(x)从点 \(x\) 开始找到最近的点。
这四个函数都是 \(O(\log^2 n)\) 的，其中 Modify_Edge(x,y) 常数最大（涉及到 \(\log\) 次区间加。
inline void build_vert(int x,ll y){
int cur=x;
while(cur!=0){
build(root[cur],dfn[x],x,y,1,n);
cur=fa[cur];
}
}
inline void modify_vert(int x,ll y){
int cur=x;
while(cur!=0){
modify(root[cur],dfn[x],dfn[x],y,1,n);
cur=fa[cur];
}
}
inline void modify_edge(int x,int y,ll z){
if(Divid::lay[x]<Divid::lay[y])swap(x,y);
int cur=x;
while(cur){
if(bothside(cur,y,x)){
if(dfn[x]<=dfn[y]){
modify(root[cur],1,dfn[y]-1,z,1,n);
modify(root[cur],dfn[y]+sz[y],n,z,1,n);
}else{
modify(root[cur],dfn[x],dfn[x]+sz[x]-1,z,1,n);
}
}else{
if(dfn[y]<=dfn[x]){
modify(root[cur],1,dfn[x]-1,z,1,n);
modify(root[cur],dfn[x]+sz[x],n,z,1,n);
}else{
modify(root[cur],dfn[y],dfn[y]+sz[y]-1,z,1,n);
}
}
cur=fa[cur];
}
}
inline int query(int x){
twomax ans=sg[root[x]].res;
int cur=fa[x];
while(cur!=0){
twomax res=sg[root[cur]].res;
res+=dis(x,cur);
ans=(ans+res),cur=fa[cur];
}
if(ans.r1.m==x){
return ans.r2.m;
}
return ans.r1.m;
}
卡常：此处即为空间的界限，只得到此，不得僭越
我们分析这个算法的空间复杂度。看上去，每个点贡献 \(\log n\) 次，每次增加 \(\log n\) 的代价这个算法是 \(O(n\log^2 n)\) 的空间复杂度。但是这样是可以直接用二叉树卡掉的，果真如此吗？
我们分析二叉树如何卡这个算法，然后我们发现，二叉树上顶端的点几乎都是满的，而满的线段树是 \(O(n)\) 的。所以“上面”的点每个点再怎么多也不会超过 \(O(n)\) 个。
然后我们根号分析。深度不超过 \(\dfrac{\log_2 n}{2}\) 的 \(\sqrt{n}\) 个点（\(2^{\dfrac{\log_2 n}{2}}=\sqrt{2^{\log_2 n}}=\sqrt{n}\)），我们就假设它们都是满的，总空间 \(O(n\sqrt{n})\)。对于深度超过 \(\dfrac{\log n}{2}\) 的点，每个点最多管辖 \(\sqrt{n}\) 个点（和上面同理），总空间也是 \(O(n\sqrt{n})\)。
所以，我们把这个算法的空间复杂度上界分析到了 \(O(n\sqrt{n})\)，但是凭借这个空间复杂度也是不太可能通过的。我们还需要进一步收缩上界。
在了解正解之前，我们需要了解本题的另一个算法。
也就是，我们在每个分治重心内部将其管辖的所有节点排列，建出完整的线段树。对 \(n\) 个点建立线段树是 \(O(n)\) 的。而每个点会被贡献 \(O(n\log n)\) 次，所以总的空间复杂度显而易见是 \(O(n\log n)\) 的。
然后我们考虑现在的做法，其实，我们每个分治子树，对应到线段树的坐标上也是一段近似区间的部分。所以我们其实是对这个区间建立了一个类似满二叉树的东西，然后从根连了一条链到这个小线段树。那么，我们的做法也是 \(O(n\log n)\) 的。
而且，这个做法相较于显然 \(O(n\log n)\) 的做法还是存在优势的。因为建立完整的线段树理论所需要的空间是 \(2n\)，但是实际上为了下标访问的合法性，我们需要 \(4n\) 的空间来建立。在只有 256MB 的原题上，这多出来的开销是致命的，致使我们不得不使用内存池等手段优化。
但是动态开点线段树天然不会存在这个下标访问合法的问题，所以轻轻松松就能卡进原题的空间限制。
struct edge{
int b;ll w;
edge(int _b,ll _w){
b=_b,w=_w;
}
};
int n,m,t,x,y;ill z,val[100005];
int root[100005],fa[100005];
vt<edge>tr[100005],vv[100005];
int dfn[100005],sz[100005],ti;
namespace Divid{
int lay[100005],del[100005];
inline void getsz(int x,int p){
sz[x]=1;
for(auto e:tr[x])if(!del[e.b]&&e.b!=p){
getsz(e.b,x);sz[x]+=sz[e.b];
}
}
inline int getcen(int x,int p,int tot){
for(auto e:tr[x])if(!del[e.b]&&e.b!=p){
if(2*sz[e.b]>=tot)return getcen(e.b,x,tot);
}return x;
}
inline int Build(int x,int l){
getsz(x,0);int s=getcen(x,0,sz[x]);
del[s]=1;lay[s]=l;
for(auto e:tr[s])if(!del[e.b]){
int ls=Build(e.b,l+1);
fa[ls]=s;vv[s].pb({ls,0});
}
return s;
}
}
struct twomax{
struct mxx{
int m;ll v;
mxx(int _m,ll _v){
m=_m,v=_v;
}
mxx(){
m=-1,v=-4e18;
}
void operator +=(const ll b){
v+=b;
}
bool operator >(const mxx b)const{
if(v==b.v)return m<b.m;
return v>b.v;
}
}r1,r2;
twomax(){
r1=mxx();r2=mxx();
}
twomax(int x,ll v){
r1=mxx(x,v);r2=mxx();
}
void operator +=(const mxx b){
if(b>r1){
if(r1.m!=b.m)r2=r1;
r1=b;
}
else if(b>r2&&b.m!=r1.m)r2=b;
}
void operator +=(const ll b){
r1+=b,r2+=b;
}
twomax operator +(twomax b){
twomax res=b;
res+=r1;res+=r2;
return res;
}
};
namespace Segtree{
struct node{
int ls,rs;ll tg;twomax res;
}sg[4680005];
int cnt=0;
inline int newnode(){
int x=++cnt;
sg[x].res=twomax();sg[x].ls=0,sg[x].rs=0;
return x;
}
inline void update(int i){
sg[i].res=(sg[sg[i].ls].res+sg[sg[i].rs].res);
}
inline void pushdown(int i){
if(!i||!sg[i].tg)return;
sg[i].res+=sg[i].tg;
if(sg[i].ls)sg[sg[i].ls].tg+=sg[i].tg;
if(sg[i].rs)sg[sg[i].rs].tg+=sg[i].tg;
sg[i].tg=0;
}
inline void build(int &i,int x,int ix,ll v,int l,int r){
if(!i)i=newnode();
pushdown(i);
if(l==r){
sg[i].res=twomax(ix,v);
return;
}int mid=(l+r)>>1;
if(x<=mid)build(sg[i].ls,x,ix,v,l,mid);
else build(sg[i].rs,x,ix,v,mid+1,r);
update(i);
}
inline void modify(int i,int L,int R,ll v,int l,int r){
if(!i)return;
pushdown(i);
if(L>r||R<l)return;
if(L<=l&&r<=R){
sg[i].tg+=v;
pushdown(i);
return;
}
int mid=(l+r)>>1;
modify(sg[i].ls,L,R,v,l,mid);
modify(sg[i].rs,L,R,v,mid+1,r);
update(i);
}
inline ll qry(int i,int x,int l,int r){
pushdown(i);
if(l==r)return sg[i].res.r1.v;
int mid=(l+r)>>1;
ll res=0;
if(x<=mid){
res=qry(sg[i].ls,x,l,mid);
pushdown(sg[i].rs);
}else {
res=qry(sg[i].rs,x,mid+1,r);
pushdown(sg[i].ls);
}update(i);
return res;
}
}using namespace Segtree;
namespace Distance{
inline void build_distance(int x,int p){
dfn[x]=++ti,sz[x]=1;
for(auto e:tr[x])if(e.b!=p)build_distance(e.b,x),sz[x]+=sz[e.b];
}
inline ll dis(int x,int y){
ll res=qry(root[y],dfn[x],1,n)-val[x];
return res;
}
inline bool bothside(int z,int y,int x){
if(dfn[x]<=dfn[y]){//x是y的祖先
return (dfn[y]<=dfn[z]&&dfn[z]<dfn[y]+sz[y]);
}else{//y是x的祖先
return !(dfn[x]<=dfn[z]&&dfn[z]<dfn[x]+sz[x]);
}
}
}using namespace Distance;
int rt=0;
inline void build_vert(int x,ll y){
int cur=x;
while(cur!=0){
build(root[cur],dfn[x],x,y,1,n);
cur=fa[cur];
}
}
inline void modify_vert(int x,ll y){
int cur=x;
while(cur!=0){
modify(root[cur],dfn[x],dfn[x],y,1,n);
cur=fa[cur];
}
}
inline void modify_edge(int x,int y,ll z){
if(Divid::lay[x]<Divid::lay[y])swap(x,y);
int cur=x;
while(cur){
if(bothside(cur,y,x)){
if(dfn[x]<=dfn[y]){
modify(root[cur],1,dfn[y]-1,z,1,n);
modify(root[cur],dfn[y]+sz[y],n,z,1,n);
}else{
modify(root[cur],dfn[x],dfn[x]+sz[x]-1,z,1,n);
}
}else{
if(dfn[y]<=dfn[x]){
modify(root[cur],1,dfn[x]-1,z,1,n);
modify(root[cur],dfn[x]+sz[x],n,z,1,n);
}else{
modify(root[cur],dfn[y],dfn[y]+sz[y]-1,z,1,n);
}
}
cur=fa[cur];
}
}
inline int query(int x){
twomax ans=sg[root[x]].res;
int cur=fa[x];
while(cur!=0){
twomax res=sg[root[cur]].res;
res+=dis(x,cur);
ans=(ans+res),cur=fa[cur];
}
if(ans.r1.m==x){
return ans.r2.m;
}
return ans.r1.m;
}
map<int,ll>mp[100005];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
sg[0].res=twomax();
rp(i,n)cin>>val[i];
rp(i,n-1){
cin>>x>>y>>z;z=-z;
tr[x].pb({y,z});mp[y][x]=z;
tr[y].pb({x,z});mp[x][y]=z;
}
rt=Divid::Build(1,0);
build_distance(1,0);
rp(i,n)build_vert(i,val[i]);
rp(i,n)for(auto e:tr[i])if(e.b<i){
modify_edge(e.b,i,e.w);
}
int ans=1;
rp(_,m){
cin>>t;
if(t==1){
cin>>x>>z;
modify_vert(x,z-val[x]);
val[x]=z;
}else{
cin>>x>>y>>z;z=-z;
modify_edge(x,y,z-mp[x][y]);
mp[x][y]=mp[y][x]=z;
}ans=query(ans);
cout<<ans<<" ";
}
return 0;
}
//Crayan_r