C++14(g++5.4) 解法, 执行用时: 66ms, 内存消耗: 4068K, 提交时间: 2019-07-14 17:37:38

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+10;
const int M=1e9+7;
int head[N],Next[N],edge[N],ver[N],num[N],n,tot;
long long ans;
void add(int x,int y,int z){
    ver[++tot]=y;edge[tot]=z;Next[tot]=head[x];head[x]=tot;
}
void dfs(int x,int y){
    num[x]=1;
    for(int i=head[x];i;i=Next[i]){
        if(ver[i]==y)continue;
        dfs(ver[i],x);
        num[x]+=num[ver[i]];
        ans=(ans+1ll*num[ver[i]]*(n-num[ver[i]])%M*edge[i]%M)%M;
    }
}
int main(){
    int x,y,z;cin>>n;
    for(int i=1;i<n;++i)scanf("%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,z);
    dfs(1,0);
    cout<<ans<<endl;
}

C++11(clang++ 3.9) 解法, 执行用时: 129ms, 内存消耗: 10072K, 提交时间: 2019-06-22 13:00:35

#include<bits/stdc++.h>
#define maxn 100005
#define mod 1000000007
using namespace std;
typedef long long ll;
ll n;
ll sum;
vector<pair<ll,ll> >mp[maxn];
ll dp[maxn];
void dfs(ll x,ll f){
	dp[x]=1;
	for(int i=0;i<mp[x].size();i++){
		ll v=mp[x][i].first;
		if(v==f) continue;
		dfs(v,x);
		sum=(sum+(n-dp[v])*dp[v]%mod*mp[x][i].second)%mod;
		dp[x]+=dp[v];
	}
}
int main(){
	cin>>n;
	ll a,b,c;
	for(int i=0;i<n-1;i++){
		cin>>a>>b>>c;
		mp[a].push_back(make_pair(b,c));
		mp[b].push_back(make_pair(a,c));
	}
	dfs(1,-1);
	cout<<sum;
}