Piggy and Trees：把路径拆成边的思维题。
思路
一看到这题的路径，就想到了 Luogu P3177 树上染色 这题化路径为边的贡献，分别计算的思维。
那么对于此题，先来观察题目里式子的意思：对于树上的每个无序点对，求出树上每个点 到这些点对之间的最短路径的 距离之和。枚举点对对应的就是前两个 \(\sum\) ，枚举每个点到最短路径的最短距离就是最后一个 \(\sum\) 。
那么对于一条无向边 \((u,v)\) ，我们可以画出如下图：
假设当前计算贡献的边是 \((1,2)\) ，先来计算 \(v\) ，也就是 \(2\) 下面的路径：
显然，以 \(2\) 为根的子树下面有 \(3\) 个节点，我们从中选出两个点组成路径，就有 \(C_{3}^{2}\) 种选法。因此，假设 \(sz[u]\) 表示以 \(u\) 为根的子树的大小，那么 \(v\) 下面我们就可以选出 \(C_{sz[v]}^{2}\) 条路径。
对于这些路径，我们要让其他点到这些路径的最短路径经过边 \((u,v)\) ，就得枚举 \(u\) 上面的节点。显然，\(1\) 上面的节点有 \(1,3,4,7\) 这 \(4\) 个，对应到全部情况上，便是有 \(sz[root]-sz[v]\) 个节点。
那么这条边对 \(v\) 下面的路径的贡献便是：
\[(sz[root]-sz[v])\times C_{sz[v]}^{2} \]对 \(u\) 上面的路径同理，贡献是：
\[sz[v]\times C_{(sz[root]-sz[v])}^{2} \]这个过程可以通过遍历一遍树来实现。
注意是 \(sz[root]-sz[v]\) 而不是 \(sz[u]-sz[v]\) ，调了我 20min，到赛后 5min 才调出来 。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
const ll mod=1e9+7;
ll sz[200005],ans=0;
int n;
vector<int>g[200005];
void dfs(int u,int fa)
{
sz[u]=1;
for(auto v:g[u])
{
if(v==fa)continue;
dfs(v,u);
sz[u]+=sz[v];
}
}
void dfs2(int u,int fa)
{
for(auto v:g[u])
{
if(v==fa)continue;
dfs2(v,u);
ans=(ans+((1ll*sz[v]*(sz[v]-1)/2)%mod*(sz[1]-sz[v])%mod))%mod;
ans=(ans+((1ll*(sz[1]-sz[v])*(sz[1]-sz[v]-1)/2)%mod*sz[v]%mod))%mod;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n-1;i++)
{
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,0);
dfs2(1,0);
cout<<ans;
return 0;
}