题解：P16826 [AFOI 2025] C.道路修复
钦定
先预处理出每个点子树内外的静态最远和次远点，可以用换根 dp+线段树动态维护区间最大次大值及下标。
一次操作会把以
一个菊花可能是一棵子树或者整棵树去掉一棵子树。再开一棵线段树维护一个编号
- 如果菊花是
y 为根的子树记为y 。 - 如果菊花是以
y 为根，整树去掉y 的儿子z 则记为-z 。
修改操作时将菊花所有的叶子（即不包括根）赋值。每次操作前先进行检查，如果根被赋值过则这次操作是无效的（因为根已经是叶子了），跳过它。
查询操作答案有这么几类：
- 原树
s 的最远距离，已经预处理了。 - 如果
id_s>0 ，找出id_s 为根子树的最远和次远点。如果s 是最远点，答案为最远点距离加上次远点距离。否则答案为最远点距离加上s 到id_s 的距离。 - 如果
id_s<0 ，找出整树去掉id_s 子树的最远和次远点。如果s 是最远点，答案为最远点距离加上次远点距离。否则答案为最远点距离加上s 到fa_{id_s} 的距离。
:::info[代码共 5.5k，去掉缺省源 3.3k。]
#include<bits/stdc++.h>
#define il inline
#define ui unsigned int
#define ll long long
#define ull unsigned ll
#define lll __int128
#define db double
#define ldb long double
#define pii pair<int,int>
#define vi vector<int>
#define vpii vector<pii>
#define fir first
#define sec second
#define gc getchar
#define pc putchar
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define pct __builtin_popcount
#define mst(a,x) memset(a,x,sizeof a)
#define mcp(a,b) memcpy(a,b,sizeof b)
using namespace std;
const int N=5e5+10,INF=0x3f3f3f3f,MOD=998244353;
const ll INFll=0x3f3f3f3f3f3f3f3f;
il int rd() {int x=0,f=1; char ch=gc(); while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=gc();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc(); return x*f;}
il ll rdll() {ll x=0; int f=1; char ch=gc(); while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=gc();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc(); return x*f;}
il void wr(int x) {if(x==INT_MIN) return printf("-2147483648"),void(); if(x<0) return pc('-'),wr(-x); if(x<10) return pc(x+'0'),void(); wr(x/10),pc(x%10+'0');}
il void wrll(ll x) {if(x==LLONG_MIN) return printf("-9223372036854775808"),void(); if(x<0) return pc('-'),wrll(-x); if(x<10) return pc(x+'0'),void(); wrll(x/10),pc(x%10+'0');}
il void wr(int x,const char *s) {wr(x),printf("%s",s);}
il void wrll(ll x,const char *s) {wrll(x),printf("%s",s);}
il int vmod(int x) {return x>=MOD?x-MOD:x;}
il int vadd(int x,int y) {return vmod(x+y);}
il int vsub(int x,int y) {return vmod(x-y+MOD);}
il int vmul(int x,int y) {return 1ll*x*y%MOD;}
il int qpow(int x,int y) {int r=1; for(;y;y>>=1,x=vmul(x,x)) if(y&1) r=vmul(r,x); return r;}
il void cadd(int &x,int y) {x=vmod(x+y);}
il void csub(int &x,int y) {x=vmod(x-y+MOD);}
il void cmul(int &x,int y) {x=vmul(x,y);}
il void cmax(int &x,int y) {x<y&&(x=y);}
il void cmaxll(ll &x,ll y) {x<y&&(x=y);}
il void cmin(int &x,int y) {x>y&&(x=y);}
il void cminll(ll &x,ll y) {x>y&&(x=y);}
int n,id,hd[N],ac[N][20],d[N],L[N],R[N],rk[N],w[N];
ll ds[N];
struct EDGE {int to,w,ne;} e[N*2];
int idx;
il void add(int u,int v,int w) {e[++id]={v,w,hd[u]},hd[u]=id;}
void dfs(int u,int fa) {
ac[u][0]=fa,d[u]=d[fa]+1,L[u]=++idx,rk[idx]=u;
for(int i=1;i<20;i++) ac[u][i]=ac[ac[u][i-1]][i-1];
for(int i=hd[u],v;i;i=e[i].ne) if((v=e[i].to)!=fa)
ds[v]=ds[u]+e[i].w,w[v]=e[i].w,dfs(v,u);
R[u]=idx;
}
int jp(int u,int k) {
for(int i=19;~i;i--) if(k>>i&1) u=ac[u][i];
return u;
}
int lca(int u,int v) {
if(d[u]<d[v]) swap(u,v);
for(int i=19;~i;i--) if(d[ac[u][i]]>=d[v]) u=ac[u][i];
if(u==v) return u;
for(int i=19;~i;i--) if(ac[u][i]!=ac[v][i]) u=ac[u][i],v=ac[v][i];
return ac[u][0];
}
#define pli pair<ll,int>
#define pll pair<pli,pli>
pll mg(pll a,pll b) {
pll rs;
if(a.fir>b.fir) rs.fir=a.fir,rs.sec=max(a.sec,b.fir);
else rs.fir=b.fir,rs.sec=max(a.fir,b.sec);
return rs;
}
struct SGT {
#define ls (id<<1)
#define rs (id<<1|1)
#define mid (l+r>>1)
#define all 1,1,n
#define Ls ls,l,mid
#define Rs rs,mid+1,r
pll tr[N*4];
ll tg[N*4];
il void ad(int id,ll k) {
tr[id].fir.fir+=k;
if(tr[id].sec.sec) tr[id].sec.fir+=k;
tg[id]+=k;
}
il void pd(int id) {ad(ls,tg[id]),ad(rs,tg[id]),tg[id]=0;}
void bld(int id,int l,int r) {
if(l==r) return tr[id]={{ds[rk[l]],rk[l]},{0,0}},void();
bld(Ls),bld(Rs),tr[id]=mg(tr[ls],tr[rs]);
}
void upd(int id,int l,int r,int L,int R,int k) {
if(L>R) return; if(L<=l&&r<=R) return ad(id,k);
pd(id),L<=mid?upd(Ls,L,R,k):void(),R>mid?upd(Rs,L,R,k):void(),tr[id]=mg(tr[ls],tr[rs]);
}
pll qry(int id,int l,int r,int L,int R) {
if(L>R) return {{0,0},{0,0}}; if(L<=l&&r<=R) return tr[id];
pd(id);
if(L<=mid&&R>mid) return mg(qry(Ls,L,R),qry(Rs,L,R));
if(L<=mid) return qry(Ls,L,R);
return qry(Rs,L,R);
}
} sgt;
pll f[N],g[N];
void dfs2(int u,int fa,int fr) {
f[u]=mg(sgt.qry(all,1,L[u]-1),sgt.qry(all,R[u]+1,n));
g[u]=sgt.qry(all,L[u],R[u]);
for(int i=hd[u],v;i;i=e[i].ne) if((v=e[i].to)!=fa) {
sgt.upd(all,1,L[v]-1,e[i].w),sgt.upd(all,L[v],R[v],-e[i].w),sgt.upd(all,R[v]+1,n,e[i].w);
dfs2(v,u,e[i].w);
sgt.upd(all,1,L[v]-1,-e[i].w),sgt.upd(all,L[v],R[v],e[i].w),sgt.upd(all,R[v]+1,n,-e[i].w);
}
}
struct S2 {
int vl[N*4],tg[N*4];
il void ad(int id,int k) {vl[id]=tg[id]=k;}
il void pd(int id) {if(tg[id]) ad(ls,tg[id]),ad(rs,tg[id]),tg[id]=0;}
void upd(int id,int l,int r,int L,int R,int k) {
if(L>R) return; if(L<=l&&r<=R) return ad(id,k);
pd(id),L<=mid?upd(Ls,L,R,k):void(),R>mid?upd(Rs,L,R,k):void();
}
int qry(int id,int l,int r,int x) {
if(l==r) return vl[id];
pd(id); return x<=mid?qry(Ls,x):qry(Rs,x);
}
} sgt2;
void QwQ() {
n=rd();
for(int i=1,u,v,w;i<n;i++) u=rd(),v=rd(),w=rd(),add(u,v,w),add(v,u,w);
dfs(1,0),sgt.bld(all),dfs2(1,0,0);
int m=rd();
for(int o,x,y;m--;) {
o=rd(),x=rd();
if(o==1) {
y=rd();
if(L[y]<=L[x]&&R[x]<=R[y]) {
int z=jp(x,d[x]-d[y]-1),c=sgt2.qry(all,L[y]);
if(!c) sgt2.upd(all,1,L[y]-1,-z),sgt2.upd(all,L[y]+1,L[z]-1,-z),sgt2.upd(all,R[z]+1,n,-z);
} else {
int c=sgt2.qry(all,L[y]);
if(!c) sgt2.upd(all,L[y]+1,R[y],y);
}
} else {
ll as=max(f[x].fir.fir,g[x].fir.fir);
int c=sgt2.qry(all,L[x]);
if(c) {
if(c>0) {
if(g[c].fir.sec==x) cmaxll(as,g[c].fir.fir+g[c].sec.fir);
else cmaxll(as,ds[x]+ds[c]-ds[lca(x,c)]*2+g[c].fir.fir);
} else {
c=-c;
if(f[c].fir.sec==x) cmaxll(as,f[c].fir.fir+f[c].sec.fir-w[c]*(!!f[c].fir.sec+!!f[c].sec.sec));
else cmaxll(as,ds[x]+ds[c]-ds[lca(x,c)]*2+f[c].fir.fir-w[c]*(1+!!f[c].fir.sec));
}
}
wrll(as,"\n");
}
// for(int i=1;i<=n;i++) wr(sgt2.qry(all,i)," "); puts("");
}
}
signed main() {
// freopen("in.in","r",stdin),freopen("out.out","w",stdout);
int T=1; while(T--) QwQ();
}