xyz, C++ (gcc) - rextester

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