#include #include #include #include #include #include #include #include #include #include #include #include #define vll vector #define vvvl vector #define vvl vector> #define VV(a, b, c, d) vector>(a, vector(b, c)) #define VVV(a, b, c, d) vector(a, vvl(b, vll (c, d))); #define re(c, b) for(ll c=0;c> G(1000001, vector()); vll dist(1000001, 0); vll c(1000001, 0); vll ans(1000001, 0); map mp; void f(ll now, ll from){ //vvl p; for(auto e:G[now]){ if(e.to==from) continue; f(e.to, now); //子の数だけ //p.push_back({dist[e.to] + c[e.to]*e.w, c[e.to]}); ans[now] += dist[e.to] + c[e.to]*e.w; dist[now] += dist[e.to] + c[e.to]*e.w; c[now] += c[e.to]; } /* for(int i=0;i> n; set st; rep(i, 1, n+1) st.insert(i); re(i, n-1){ ll a, b, c=1;std::cin >> a >> b; G[a].push_back({b, c}); G[b].push_back({a, c}); st.erase(b); } f((*st.begin()), -1); //std::cout << (*st.begin()) << '\n'; ll s = 0; for(int i=1;i<=n;i++) s += ans[i]; std::cout << s << '\n'; }