MTREE - Another Tree Problem
Tác giả: skyvn97
Ngôn ngữ: C++
#include<cstdio>
#include<vector>
#include<cstring>
#define MAX 100100
#define p first
#define s second
using namespace std;
typedef long long ll;
const ll mod=(ll)1e9+7;
typedef pair<int,ll> ii;
vector<ii> g[MAX];
int c[MAX];
int n;
ll f[MAX];
ll res;
void loadgraph(void) {
int i;
int u,v;
ll cst;
scanf("%d",&n);
for (i=1;i<=n;i=i+1) g[i].clear();
for (i=1;i<n;i=i+1) {
scanf("%d",&u);
scanf("%d",&v);
scanf("%lld",&cst);
g[u].push_back(ii(v,cst));
g[v].push_back(ii(u,cst));
}
memset(f,0,sizeof f);
memset(c,0,sizeof c);
res=0;
}
void visit(const int &u) {
int i,v;
//printf("Visiting %d\n",u);
for (i=0;i<g[u].size();i=i+1)
if (c[g[u][i].p]==0) {
v=g[u][i].p;
c[v]=1;
visit(v);
//printf("f(%d)=%lld\n",v,f[v]);
res=(res+f[v])%mod;
res=(res+((f[v]*g[u][i].s+g[u][i].s)%mod)*f[u])%mod;
f[u]=(f[u]+f[v]*g[u][i].s+g[u][i].s)%mod;
//printf("res is now %lld\n",res);
}
}
void process(void) {
c[1]=1;
visit(1);
printf("%lld",(res+f[1])%mod);
}
int main(void) {
loadgraph();
process();
return 0;
}