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

题目描述
红红和蓝蓝是随机降生在苹果树上的苹果仙灵，现在红线仙想估测他们的CP系数，并决定是否使他们成为一对CP。
给出n个结点n-1条边的树，节点编号为1到n,定义distance(i,j)为i与j的树上距离。
CP系数是指所有红红和蓝蓝在不同位置i,j的distance(i,j)之和。
即∑n−1i=1∑nj=i+1distance(i,j)
求红红和蓝蓝的CP系数，对10^9+7取模。
输入描述:

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

输出描述:

一行一个整数，表示CP系数对10^9+7取模的结果。

示例1
输入
复制

4
1 2 1
2 3 1
2 4 1

输出
复制

9

说明

distance(1,2)=1
distance(1,3)=2
distance(1,4)=2
distance(2,3)=1
distance(2,4)=1
distance(3,4)=2
CP系数=(1+2+2+1+1+2)%(10^9+7)=9

将一条边删去后，分成的两棵子树内的点都需要经过这条边才能到达另一棵子树，它对结果的贡献为

左端结点个数∗右端节点个数∗权值

 

鲲神的树就是nb

//摸鲲神
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const int mod=1e9+7;
struct node{
	int v,w;
	node(){
	}
	node(int _v,int _w){
		v=_v;
		w=_w;
	}
};
int num[N];
vector<node> G[N];
int n;
ll ans=0;
void dfs(int u,int fa){
	num[u]=1;
	for(int i=0;i<G[u].size();i++){
		int v=G[u][i].v;
		if(v==fa) continue;
		dfs(v,u);
		ans+=(ll)num[v]*(n-num[v])%mod*G[u][i].w%mod;
		ans%=mod;
		num[u]+=num[v];
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		G[u].push_back(node(v,w));
		G[v].push_back(node(u,w));
	}
	dfs(1,0);
	printf("%lld\n",ans);
	return 0;
}