题目分析

我们先考虑 $\operatorname{joy}(u,v)$ 怎么的到。我们首先希望第一步去一个距离 $u$ 很远的点、倒数第一步从一个距离 $v$ 很远的点回来。我们尝试让这两个点分别是距离 $u,v$ 最远的点。根据经典结论，这样的点一定是树的直径的两个段点之一（如果有多个直径取任意一个就行）。

这里不妨假定上述两点是 $u',v'$。由此，$\operatorname{joy}(u,v)$ 至多是 $\min(\operatorname{dis}(u,u'),\operatorname{dis}(v,v'))$。我们发现如果这两个距离极远的点是相同的，那么可以取到；如果不同，那么 $\operatorname{dis}(u',v')$ 是更长的，也可以取到。

所以问题转化为 $\sum\limits_{x,y\in[1,n],x\ne y}\min(\operatorname{dis}(x,x'),\operatorname{dis}(y,y'))$。这个东西直接拆贡献就行。

总时间复杂度 $O(n\log n)$。

其实应该可以用基数排序和 DFS 序、线性 RMQ 求 LCA 做到 $O(n)$。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N=5e5+1,p=1e9+7;
int n,a[N],dep[N],depth[N],g[N][21],depest[N],dlen,ans;
pair<int,int>diameter;
vector<pair<int,int> >e[N];
void dfs(int u,int lstlen,int fath){
    g[u][0]=fath;
    depth[u]=depth[fath]+1,dep[u]=dep[fath]+lstlen;
    for(auto[v,w]:e[u]){
        if(v==fath)
            continue;
        dfs(v,w,u);
    }
    return;
}
void init(){
    for(int j=1;j<=20;j++)
        for(int i=1;i<=n;i++)
            g[i][j]=g[g[i][j-1]][j-1];
    return;
}
int qlca(int u,int v){
    if(depth[u]<depth[v])
        swap(u,v);
    for(int i=20;~i;i--)
        if(depth[g[u][i]]>=depth[v])
            u=g[u][i];
    for(int i=20;~i;i--)
        if(g[u][i]!=g[v][i])
            u=g[u][i],v=g[v][i];
    return u==v?u:g[v][0];
}
int qdis(int u,int v){
    int lca=qlca(u,v);
    return dep[u]+dep[v]-2*dep[lca];
}
void findd(int u,int fath){
    depest[u]=u;
    for(auto[v,w]:e[u]){
        if(v==fath)
            continue;
        findd(v,u);
        if(qdis(depest[u],depest[v])>dlen)
            dlen=qdis(depest[u],depest[v]),diameter={depest[u],depest[v]};
        if(dep[depest[v]]>dep[depest[u]])
            depest[u]=depest[v];
    }
    return;
}
int travel(vector<signed>U,vector<signed>V,vector<signed>W){
    n=U.size()+1;
    for(auto&p:U)
        p++;
    for(auto&p:V)
        p++;
    for(int i=0,u,v,w;i<n-1;i++){
        u=U[i],v=V[i],w=W[i];
        e[u].push_back({v,w}),e[v].push_back({u,w});
    }
    dfs(1,0,0),init(),findd(1,0);
    for(int i=1;i<=n;i++)
        a[i]=max(qdis(i,diameter.first),qdis(i,diameter.second));
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
        (ans+=((a[i]%p)*(2*(n-i)))%p)%=p;
    return ans;
}