#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){ int l = H.lca(u,v); mint ret = S[u] + S[v] - S[l]*2; return ret; } int main(){ int n; cin>>n; vector> E(n); vector>> E2(n); 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].emplace_back(v,w); E2[v].emplace_back(u,w); } centroid_tree C(E); HLD H(E); vector dis(n,0); vector visited(n,false); queue Q; Q.push(0); visited[0] = true; while(Q.size()>0){ int u = Q.front(); Q.pop(); rep(i,E2[u].size()){ int v = E2[u][i].first; mint w = E2[u][i].second; if(visited[v])continue; visited[v] = true; dis[v] = dis[u] + w; Q.push(v); } } mint ans = 0; rep(i,n){ mint sum = 0; mint temp = 0; int cur = 0; rep(j,C.childs[i].size()){ mint d = get_dis(H,dis,i,C.childs[i][j]); ans += d*d * (C.bind[i].back() - (C.bind[i][cur+1] - C.bind[i][cur])); ans += d*2*sum; temp += d; if(j+1 == C.bind[i][cur+1]){ cur++; sum += temp; temp = 0; } } } cout<