Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
xyz
//g++ 7.4.0 #include <bits/stdc++.h> using namespace std; typedef long long int ll; #define pii pair<ll, ll> #define F first #define S second const int mod = 1e9+7; const int N = 3e5 + 5; vector<ll> sub(N), tot(N), ans(N); vector<pii> g[N]; void dfs(int s, int p, int cur_w) { tot[s] = tot[p] + cur_w; for (auto i : g[s]) { int w = i.S, u = i.F; if (u == p) continue; dfs(u, s, w); sub[s] += sub[u]; } sub[s] ++; } void dfs2(int s, int p, ll child, ll tot, ll w) { ans[s] = w*child - w*sub[s] + ans[p]; // cout << s << " " << p << ": " << child << " " << tot << " " << w << " " << sub[s] << " --> " << ans[s] << endl; for (auto i : g[s]) { ll u = i.F, cur_w = i.S; if (u == p) continue; dfs2(u, s, (child + sub[s] - sub[u]), tot+cur_w, cur_w); } } int main(){ ios_base :: sync_with_stdio(0); cin.tie(0); int n; cin >> n; for (int j = 0; j < n-1; j ++) { int u, v, w; cin >> u >> v >> w; g[u].push_back({v, w}); g[v].push_back({u, w}); } dfs(1, 0, 0); for (int j = 1; j <= n; j ++) cout << "(" << sub[j] << " " << tot[j] << ") "; cout << endl; dfs2(1, 0, 0, 0, 0); ll root = 0; for (int j = 1; j <= n; j ++) root += tot[j]; for (int j = 1; j <= n; j ++) cout << (ans[j] + root) << " "; return 0; } /* N 1H ==> N-1 2H ==> N-2 f(X) => (f(X-1) + f(X-2)) * 2 1 1 1 (8) 1 2 (4) 2 1 (4) */
run
|
edit
|
history
|
help
0
Boost adapters foreach
Expected GCD
SegTree
H - Subprime Fibonacci Sequence
Proyecto 1
code
new
MovConstrAssign4
Python Like C++ Overload Function Template
Boost phoenix e.g. 1 no functor