题解：P16826 [AFOI 2025] C.道路修复

· · 题解

在线纯并查集写法。

不带修的话答案显然是每个点到直径两端点的距离最大值，这部分用经典做法，以距离上一个点最远的位置为根 DFS 三遍即可。

接下来考虑带修。我们发现操作相当于将以 u 为根，v 的子树缩成一个菊花图，其中每个点到 v 的边权为其原先到 v 的距离。

发现这么修改后菊花图中的每个点可以跳到 v 再跳到除自己以外的最大边，因此我们可以对每个菊花图开一个并查集，同时存储当前对应的最大边、次大边、以及每个点到 v 的距离，查询的时候将初始答案与菊花图内的距离取最大值即可。

接下来考虑如何实现。我们可以以 v 为根对所有不含 u 的子树做 DFS，在 DFS 的过程中合并子树内的状态，然后删掉整颗子树，至于每个点到 v 的距离可以在并查集查询时同时更新。

现在的问题是怎么判断包含 u 的子树。这部分可以用 DFS 序判断，对于当前与 v 的相连的每个结点 x：

注意到缩菊花图后树的结构可能发生改变，但如果 u 在 v 的菊花图内，那么剩下的点一定不会和 u 产生包含关系，因此不需要额外处理。

因为只能用路径压缩，所以时间复杂度为 O(n+q \log n)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=500000;

int i,j,k,n,m,t,rt,it,l[N+50],r[N+50],F[N+50];
ll g[N+50],f[N+50][3],res[N+50],t1,t2;
vector<pair<int,int> > v[N+50];

int find(int x){
    if(F[x]!=x){
        int k=find(F[x]); g[x]+=g[F[x]]; F[x]=k;
    }
    return F[x];
}

void dfs0(ll d,int x,int fa){
    l[x]=++it;
    if(d>t2){t1=x; t2=d;}
    res[x]=max(res[x],d);
    for(auto [y,w]:v[x])if(y!=fa)dfs0(d+w,y,x);
    r[x]=it;
}

int _y;

void dfs2(ll d,int x,int fa){
    if(f[x][1]+d>=f[_y][1]){
        f[_y][2]=f[_y][1];
        f[_y][1]=f[x][1]+d; f[_y][0]=f[x][0];
    }
    else f[_y][2]=max(f[_y][2],f[x][1]+d);
    f[_y][2]=max(f[_y][2],f[x][2]+d);
    g[x]=d; F[x]=_y;
    for(auto [y,w]:v[x])if(y!=fa){
        dfs2(d+w,y,x);
    }
    v[x]={};
}

void upd(int x,int y){
    _y=y;
    t1=t2=0;
    for(auto [z,w]:v[y]){
        if(l[y]<=l[z]&&r[z]<=r[y]){
            if(l[z]<=l[x]&&r[x]<=r[z]){t1=z; t2=w; continue;}
        }
        else{
            if(l[x]<l[y]||l[x]>r[y]){t1=z; t2=w; continue;}
        }
        dfs2(w,z,y);
    }
    if(t1)v[y]={{t1,t2}};
    else v[y]={};
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    for(i=1;i<=n;i++){
        F[i]=i;
        f[i][0]=i; f[i][1]=0; f[i][2]=-1e18;
    }
    for(i=1;i<n;i++){
        cin>>j>>k>>m;
        v[j].push_back({k,m});
        v[k].push_back({j,m});
    }
    rt=1;
    for(int T=1;T<=3;T++){it=0; t1=rt; t2=0; dfs0(0,rt,0); rt=t1;}
    cin>>t;
    while(t--){
        int op,x,y;
        cin>>op>>x;
        if(op==1){
            cin>>y; upd(x,y);
        }
        else{
            k=find(x);
            cout<<max(res[x],g[x]+(f[k][0]==x?f[k][2]:f[k][1]))<<'\n';
        }
    }
}