dsu：P16826 [AFOI 2025] C.道路修复
fish_love_cat · · 题解
我没看到难度不按升序排序。
Bad Ending.
首先操作不会缩短距离，因此答案不会被减少。
考虑初始局面的答案，然后在这些的基础上进行修改。
有经典结论，任意一条直径的两个端点，对于任意一个点都必有至少一个端点距离该点的距离达到所有点距离该点的最大值。证明的话，考虑到如果存在一个更远的点那么以这个点为开头搜直径可以得到更长的结果，违背定义，故得证。
于是搜直径，钦定一个根然后处理 LCA 和每个点的深度来维护树上距离，于是我们就把初始局面的答案给维护出来了。
考虑操作对答案的影响。
我们把节点在操作后变成菊花叶子称做删除该节点。
容易发现被删除的节点作为灾害中心是无用的，判掉。
假设我们把灾害中心删掉，那么受灾的点就是不与
注意到受灾的点的 dfn 序环形意义下是连续的，于是可以考虑直接做白雪皑皑状物进行合并，用并查集维护并查集的合并即可。
考虑操作对于答案的影响，显然只有被删除的节点会被增加答案，增加的方式一定是走到这个菊花的根，然后再走到一样挂在这个菊花上被删除的点。
显然后面这个选择要尽量大且不能选到第一个点，于是我们并查集维护的时候对每个连通块维护最长边和次长边即可，不需要维护所有信息，故可以快速合并。
时间复杂度是
哎我说真的这题的性价比严格低于去打部分分，部分分给太多了写这个题完全没意义啊。
输麻了。
update：修了个锅，感谢 @haoertiansuo 的提醒。
这个史山可能到处都是锅，欢迎大家来叉。
#include<bits/stdc++.h>
#define int long long
#define N 500005
using namespace std;
vector<pair<int,int>>ve[N];
int ans[N],dfn[N],dfnn;
int dep[N],mxdep[N],mxid[N];
int dis[N],l[N],r[N],pm[N];
int deep[N];
int fa[25][N];
int mi[25][N];
int get(int u,int v){
if(dfn[u]<dfn[v])return u;
return v;
}
int lg[N];
int lca(int u,int v){
if(u==v)return u;
u=dfn[u],v=dfn[v];
if(u>v)swap(u,v);
int g=lg[v-u];
return get(mi[g][u+1],mi[g][v-(1<<(g))+1]);
}
void dfsiz(int x,int fath){
dfn[x]=++dfnn;
pm[dfnn]=x;
mi[0][dfn[x]]=fath;
fa[0][x]=fath;
mxdep[x]=dep[x];
deep[x]=deep[fath]+1;
mxid[x]=x;
l[x]=dfnn;
for(pair<int,int>i:ve[x])
if(i.first!=fath){
dep[i.first]=dep[x]+i.second;
dfsiz(i.first,x);
if(mxdep[x]<mxdep[i.first])
mxdep[x]=mxdep[i.first],mxid[x]=mxid[i.first];
}
r[x]=dfnn;
}
int A,B,est;
void dfs(int x,int fa){
for(pair<int,int>i:ve[x])
if(i.first!=fa){
dis[i.first]=dis[x]+i.second;
dfs(i.first,x);
}
}
int fd[N],mx[2][N],mxi[N];
bool vis[2][N];
int find(int x){
return x==fd[x]?x:fd[x]=find(fd[x]);
}
int fa2[N];
int find2(int x){
return x==fa2[x]?x:fa2[x]=find2(fa2[x]);
}
signed main(){
for(int i=2;i<N;i<<=1)
lg[i]=1;
for(int i=1;i<N;i++)
lg[i]+=lg[i-1];
int n;
cin>>n;
for(int i=1;i<=n+1;i++)
fd[i]=i,fa2[i]=i;
for(int i=1;i<n;i++){
int u,v,w;
cin>>u>>v>>w;
ve[u].push_back({v,w});
ve[v].push_back({u,w});
}
dfsiz(1,0);
for(int i=1;i<=20;i++)
for(int j=1;j+(1<<i)-1<=n;j++)
mi[i][j]=get(mi[i-1][j],mi[i-1][j+(1<<(i-1))]);
for(int i=1;i<=20;i++)
for(int j=1;j<=n;j++)
fa[i][j]=fa[i-1][fa[i-1][j]];
A=mxid[1];
dfs(mxid[1],0);
for(int i=1;i<=n;i++)
if(dis[i]>est)est=dis[i],B=i;
for(int i=1;i<=n;i++)
ans[i]=dep[i]+max(dep[A]-dep[lca(A,i)]*2,
dep[B]-dep[lca(B,i)]*2);
for(int i=1;i<=n;i++)
mxi[i]=i,vis[0][i]=1;
int q;
cin>>q;
while(q--){
int op;
cin>>op;
if(op==1){
int u,v;
cin>>u>>v;
if(dfn[v]==fd[dfn[v]]){
if(lca(u,v)==v){
for(int i=20;i>=0;i--)
if(deep[fa[i][u]]>deep[v])u=fa[i][u];
for(int i=find(1);i<l[u];i=find(i+1))
if(pm[i]!=v){
int x=pm[i];
mx[0][x]+=dep[x]+dep[v]-dep[lca(x,v)]*2;
if(vis[1][x])
mx[1][x]+=dep[x]+dep[v]-dep[lca(x,v)]*2;
if(mx[0][x]>=mx[0][v])
mx[1][v]=mx[0][v],
mx[0][v]=mx[0][x],
mxi[v]=mxi[x],vis[1][v]=1;
else if(mx[0][x]>=mx[1][v])
mx[1][v]=mx[0][x],vis[1][v]=1;
if(mx[1][x]>=mx[1][v]&&vis[1][x])
mx[1][v]=mx[1][x],vis[1][v]=1;
fa2[find2(x)]=find2(v);
fd[i]=find(i+1);
}
for(int i=find(r[u]+1);i<=n;i=find(i+1))
if(pm[i]!=v){
int x=pm[i];
mx[0][x]+=dep[x]+dep[v]-dep[lca(x,v)]*2;
if(vis[1][x])
mx[1][x]+=dep[x]+dep[v]-dep[lca(x,v)]*2;
if(mx[0][x]>=mx[0][v])
mx[1][v]=mx[0][v],
mx[0][v]=mx[0][x],
mxi[v]=mxi[x],vis[1][v]=1;
else if(mx[0][x]>=mx[1][v])
mx[1][v]=mx[0][x],vis[1][v]=1;
if(mx[1][x]>=mx[1][v]&&vis[1][x])
mx[1][v]=mx[1][x],vis[1][v]=1;
fa2[find2(x)]=find2(v);
fd[i]=find(i+1);
}
}else{
for(int i=find(l[v]+1);i<=r[v];fd[i]=find(i+1),i=find(i)){
int x=pm[i];
mx[0][x]+=dep[x]+dep[v]-dep[lca(x,v)]*2;
if(vis[1][x])
mx[1][x]+=dep[x]+dep[v]-dep[lca(x,v)]*2;
if(mx[0][x]>=mx[0][v])
mx[1][v]=mx[0][v],
mx[0][v]=mx[0][x],
mxi[v]=mxi[x],vis[1][v]=1;
else if(mx[0][x]>=mx[1][v])
mx[1][v]=mx[0][x],vis[1][v]=1;
if(mx[1][x]>=mx[1][v]&&vis[1][x])
mx[1][v]=mx[1][x],vis[1][v]=1;
fa2[find2(x)]=find2(v);
}
}
}
}else{
int x;
cin>>x;
int flc=find2(x);
int ret=ans[x];
if(dfn[x]!=fd[dfn[x]]){
if(mxi[flc]==x)
ret=max(ret,mx[1][flc]+mx[0][flc]);
else ret=max(ret,mx[0][flc]+dep[x]+dep[flc]-dep[lca(x,flc)]*2);
}
cout<<ret<<'\n';
}
}
return 0;
}
// ──比自身性命更重要的东西，应该没那么多才是。
// 那是姊夫的话。
// 姊夫说了那些话，找到比自身性命更重要的东西以后，就真的为其舍弃了性命。
// ──缇亚忒现在还是想变得像学姊一样。
// 那是对缇亚忒的评语。
// 她拚了命，追逐著憧憬之人的背影。她真的想舍弃性命。
// 希望变得像学姊一样。
// 换句话说，那表示她同样想为学妹们拓展出道路吗？
// 为了在六十八号岛的众多妹妹。
// 为了比自己一个人的命更加重要，而且生命短暂的那些家人？