题解：P11238 [KTSC 2024 R1] 铁路 2

· · 题解

更好的阅读体验

以下所有下标均从 \boldsymbol 1 开始。

题面过于冗长，用人话讲就是对于每个点对 (u, v)，定义 \text{joy}(u,v) = \max\limits_{p}\min \{\text{dis}(u,p), \text{dis}(p,v)\}，然后求 \sum \limits_{u=1}^{n} \sum \limits_{v=1}^{n} \text{joy}(u,v)。

观察这个式子 \text{joy}(u,v) = \max\limits_{p}\min \{\text{dis}(u,p), \text{dis}(p,v)\}，我们发现这个 p 点一定要是 u,v 能到达的最远点。联系到我们用两次 dfs 求树的直径的过程，我们发现这个点一定是直径的端点。

那么对于一个点 i，我们把它到直径端点的距离处理出来，称其为 maxd_i。我们先假设我们要求的是无序点对的答案，那么我们求 mxd 两两最小值之和，其实就是将 mxd 升序排序后，对于下标数对 (i,j)(i<j)，是 i 产生贡献。所以 i 位置产生贡献的区间为 [i+1,n]，长度为 n-i。求和最后 \times 2 即可。

对于实现，可以用树上倍增求出点对距离，复杂度 O(n \log n)。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 500006
#define MOD 1000000007
using namespace std;
signed travel(vector<signed> U,vector<signed> V,vector<signed> W);
int n,fa[21][N],wt[21][N],dep[N],s,t,maxd[N],maxn;
vector<pair<int,int> > G[N];
void dfs(int u)
{
    for(int i=1;i<=20;i++)
        fa[i][u]=fa[i-1][fa[i-1][u]],wt[i][u]=wt[i-1][u]+wt[i-1][fa[i-1][u]];
    for(auto [v,w]:G[u])if(v!=fa[0][u])
        fa[0][v]=u,wt[0][v]=w,dep[v]=dep[u]+1,dfs(v);
}
int getdis(int u,int v)
{
    int ret=0;
    if(dep[u]<dep[v])swap(u,v);
    for(int i=20;~i;i--)
        if(dep[fa[i][u]]>=dep[v])ret+=wt[i][u],u=fa[i][u];
    if(u==v)return ret;
    for(int i=20;~i;i--)
        if(fa[i][u]^fa[i][v])ret+=wt[i][u]+wt[i][v],u=fa[i][u],v=fa[i][v];
    return ret+wt[0][u]+wt[0][v];
}
signed travel(vector<signed> U,vector<signed> V,vector<signed> W)
{
    n=U.size()+1;
    for(int i=0;i<n-1;i++)
        G[U[i]+1].push_back({V[i]+1,W[i]}),G[V[i]+1].push_back({U[i]+1,W[i]});
    dep[1]=1,dfs(1);
    for(int i=1,tmp;i<=n;i++)
        if((tmp=getdis(1,i))>maxn)maxn=tmp,s=i;
    maxn=0;
    for(int i=1,tmp;i<=n;i++)
        if((tmp=getdis(s,i))>maxn)maxn=tmp,t=i;
    for(int i=1;i<=n;i++)maxd[i]=max(getdis(s,i),getdis(t,i));
    sort(maxd+1,maxd+1+n);
    int ret=0;
    for(int i=1;i<=n;i++)ret+=maxd[i]%MOD*(n-i)%MOD,ret%=MOD;
    return ret*2%MOD;
}