树中所有点距离之和

链接：https://ac.nowcoder.com/acm/contest/992/J
来源：牛客网

题目描述

红红和蓝蓝是随机降生在苹果树上的苹果仙灵，现在红线仙想估测他们的CP系数，并决定是否使他们成为一对CP。

给出n个结点n-1条边的树，节点编号为1到n,定义distance(i,j)为i与j的树上距离。

CP系数是指所有红红和蓝蓝在不同位置i,j的distance(i,j)之和。

即

∑i=1n−1∑j=i+1ndistance(i,j)sum_{i=1}^{n-1}{sum_{j=i+1}^{n}{distance(i,j)}}∑i=1n−1​∑j=i+1n​distance(i,j)。

求红红和蓝蓝的CP系数，对10⁹+7取模。

输入描述:

第一行一个整数n（ 1 < n <= 10⁵ ),表示树的结点个数。

随后n-1行，每行三个整数a,b,c ( 1 <= a,b <= n ),( 0 <= c <= 10⁹ )，表示结点a,b之间有一条权值为c的边,( a

输出描述:

一行一个整数，表示CP系数对10

⁹

+7取模的结果。

示例1

输入

复制

输出

复制

 1 /*
 2 
 3     树形动态规划：
 4     num[rt]: rt子树有多少节点
 5     sum[rt]: rt子树中所有子节点到rt的距离之和
 6     ans:  所有这样的点（i,j）【i,j不在同一条直线上】距离之和
 7         // sun[rt] 那么也可以表示为在同一直线上两点之和
 8 */
 9 #include <bits/stdc++.h>
10 using namespace std;
11 const int N=1e5+7;
12 const int mod=1e9+7;
13 typedef long long LL;
14 struct node {
15     int id;
16     LL val;
17 };
18 vector <node> g[N];
19 LL num[N], sum[N];
20 bool vis[N];
21 int n; LL ans;
22 void dfs (int rt) {
23     vis[rt]=1;
24     for (int i=0;i<g[rt].size();i++) {
25         int nxt=g[rt][i].id;
26         if (!vis[nxt]) {
27             dfs(nxt);
28             LL d1=(sum[nxt]+num[nxt]*g[rt][i].val)%mod;
29             ans+=(d1*num[rt]%mod+sum[rt]*num[nxt]%mod)%mod;
30             num[rt]+=num[nxt];
31             sum[rt]=(sum[rt]+d1)%mod;
32         }
33     }
34     num[rt]+=1;
35     //printf("rt: %d num: %lld sum: %lld ans: %lld
",rt, num[rt], sum[rt], ans);
36 }
37 int main ()
38 {
39     scanf("%d", &n);
40     for (int i=1;i<n;i++) {
41         int u, v; LL val; scanf("%d %d %lld", &u, &v, &val);
42         node tmp={v, val}; g[u].push_back(tmp);
43         tmp.id=u;          g[v].push_back(tmp);
44     }
45     dfs(1);
46     for (int i=1;i<=n;i++)
47         ans=(ans+sum[i])%mod;
48     printf("%lld
",ans);
49     return 0;
50 }