#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> pos; vector> bind; vector> childs; centroid_tree(vector> argE){ int n = argE.size(); E.resize(n,vector()); cnt.resize(n); r = go(0,argE); pos.resize(n); bind.resize(n); childs.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){ 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; } 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(); bind[cur].push_back(childs[cur].size()); } }; struct lca{ vector depth;//depth[i] 頂点iの深さ vector> parents;//parents[i][j] 頂点iから2^j個上の親 int max_j = 30; lca(int n,vector> &E){ depth.assign(E.size(),-1); parents.assign(E.size(),vector(max_j,-1)); stack s; s.push(n); depth[n] = 0; while(s.size()!=0){ int k = s.top(); s.pop(); for(int i=0;i=0;i--){ if(parents[u][i]!=parents[v][i]){ u = parents[u][i]; v = parents[v][i]; } } return parents[u][0]; } int get_distance(int u,int v){ return depth[u]+depth[v]-2*depth[query(u,v)]; } }; mint get_dis(lca &H,vector &S,int u,int v){ int l = H.query(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); lca H(0,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<