#include #include #include using namespace atcoder; using mint = modint1000000007; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf 1000000000000000000 struct centroid_tree{ vector> E; vector cnt; int r; vector depth; vector> pos; vector> bind; vector> childs; vector> gs; centroid_tree(vector> argE){ int n = argE.size(); E.resize(n,vector()); cnt.resize(n); r = go(0,argE); depth.resize(n); pos.resize(n); bind.resize(n); childs.resize(n); gs.resize(n); dfs(r,-1,E); build(r,0); } int go(int a,vector> &argE){ dfs(a,-1,argE); int sz = cnt[a]; int ret = dfs2(a,-1,argE,sz); rep(i,argE[ret].size()){ int to = argE[ret][i]; argE[to].erase(find(argE[to].begin(),argE[to].end(),ret)); int g = go(to,argE); E[ret].push_back(g); } argE[ret].clear(); return ret; } void dfs(int cur,int p,vector> &argE){ cnt[cur] = 1; rep(i,argE[cur].size()){ int to = argE[cur][i]; if(to==p)continue; dfs(to,cur,argE); cnt[cur] += cnt[to]; } } int dfs2(int cur,int p,vector> &argE,int sz){ int ret = -1; int m = 0; rep(i,argE[cur].size()){ int to = argE[cur][i]; if(to==p)continue; ret = dfs2(to,cur,argE,sz); if(ret!=-1)return ret; m = max(m,cnt[to]); } if(sz-cnt[cur]<=sz/2 && m<=sz/2){ ret = cur; } return ret; } void build(int cur,int d){ depth[cur] = d; bind[cur].push_back(0); rep(i,E[cur].size()){ int to = E[cur][i]; build(to,d+1); rep(j,childs[to].size()){ int x = childs[to][j]; childs[cur].push_back(x); if(pos[x].size()<=d)pos[x].resize(d+1,-1); pos[x][d] = i; if(gs[x].size()<=d)gs[x].resize(d+1,-1); gs[x][d] = cur; } bind[cur].push_back(childs[cur].size()); } int x = cur; childs[cur].push_back(x); if(pos[x].size()<=d)pos[x].resize(d+1,-1); pos[x][d] = E[cur].size(); if(gs[x].size()<=d)gs[x].resize(d+1,-1); gs[x][d] = cur; bind[cur].push_back(childs[cur].size()); } }; struct HLD{ vector sz,parent,depth,root,pos; vector arr; HLD(vector> &E){ sz.resize(E.size(),1); parent.resize(E.size(),0); depth.resize(E.size(),0); root.resize(E.size(),0); pos.resize(E.size(),0); dfs(0,-1,E); dfs2(0,-1,E,0); } void dfs(int now,int p,vector> &E){ parent[now] = p; if(p==-1){ depth[now] = 0; } else{ depth[now] = depth[p]+1; } for(int i=0;i> &E,int r){ pos[now] = arr.size(); arr.push_back(now); root[now] = r; int maxi = 0; int ind = -1; for(int i=0;i> query(int u,int v){ vector> ret; int t = 0; while(root[u]!=root[v]){ if(depth[root[u]] <= depth[root[v]]){ ret.insert(ret.begin()+t,{pos[root[v]], pos[v]}); v = parent[root[v]]; } else{ ret.insert(ret.begin()+t,{pos[u],pos[root[u]]}); u = parent[root[u]]; t++; } } ret.insert(ret.begin()+t,{pos[u],pos[v]}); return ret; } int lca(int u,int v){ for(;;v=parent[root[v]]){ if(pos[u]>pos[v])swap(u,v); if(root[u]==root[v])return u; } } int get_distance(int u,int v){ return depth[u] + depth[v] - 2 * depth[lca(u,v)]; } }; mint get_dis(HLD &H,vector &S,int u,int v){ auto t = H.query(u,v); mint ret = 0; rep(i,t.size()){ int l = t[i].first,r = t[i].second; if(l>r)swap(l,r); ret += S[r+1] - S[l]; } return ret; } int main(){ int n; cin>>n; vector> E(n); vector> E2(n*2-1); vector S(2*n,0); rep(i,n-1){ int u,v,w; scanf("%d %d %d",&u,&v,&w); u--;v--; E[u].push_back(v); E[v].push_back(u); E2[u].push_back(n+i); E2[v].push_back(n+i); E2[n+i].push_back(u); E2[n+i].push_back(v); S[n+i] = w; } centroid_tree C(E); HLD H(E2); if(n>100)return 0; { vector SS(2*n,0); rep(i,2*n-1){ SS[H.pos[i]+1] = S[i]; } rep(i,2*n-1){ SS[i+1] += SS[i]; } swap(S,SS); } vector> sum(n); rep(i,n){ sum[i].push_back(0); rep(j,C.childs[i].size()){ int u = C.childs[i][j]; mint d = get_dis(H,S,i,u); sum[i].push_back(d); } rep(j,sum[i].size()){ if(j==0)continue; sum[i][j] += sum[i][j-1]; } } mint ans = 0; rep(i,n){ rep(j,C.gs[i].size()){ int x = C.gs[i][j]; int l = C.bind[x][C.pos[i][j]]; int r = C.bind[x][C.pos[i][j]+1]; mint d = get_dis(H,S,i,x); ans += d*d * (C.bind[x].back() - (r-l)); mint s = 0; s += sum[x].back() - sum[x][r]; s += sum[x][l]; ans += s*d; } } cout<