自动搬运

查看原文

来自洛谷，原作者为

	dyc2022 「知らない世界を見せてよ」

搬运于2025-08-24 23:05:35，当前版本为作者最后更新于2025-06-28 17:17:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

更好的阅读体验

以下所有下标均从 $\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;
}