General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
45631229 Practice:
YangDavid
1076E - 16 GNU C++17 Hacked 717 ms 79356 KB 2018-11-12 19:56:23 2018-11-12 19:56:23
 
 
→ Source
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 1; i <= n; ++i)
using namespace std;
typedef long long ll;

const int maxn = 600300, maxm = 600600;
int head[maxn], nxt[maxm], ecnt = 1, n, q, dep[maxn], mxdep = 0;
ll ans[maxn];
struct edge {
    int from, to;
    edge(int f = 0, int t = 0) :
        from(f), to(t) { }
} e[maxm];
inline void addedge(int x, int y) {
    e[++ecnt] = edge(x, y);
    nxt[ecnt] = head[x];
    head[x] = ecnt;
}

map<int, ll> mp[maxn];

void dfs_dep(int v,int fa, int depth) {
    dep[v] = depth;
    if(depth > mxdep) mxdep = depth;
    for(int i = head[v]; i; i = nxt[i]) {
        int to = e[i].to;
        if(to == fa) continue;
        dfs_dep(to, v, depth + 1);
    }
}
void dfs_solve(int v,int fa) {
    ans[v] = 0;
    for(auto p : mp[v]) {
        ans[v] += p.second;
    }
    for(int i = head[v]; i ; i = nxt[i]) {
        int to = e[i].to;
        if(to == fa) continue;
        for(auto p : mp[v]) {
            if(p.first == 0) continue;
            mp[to][p.first-1] += p.second;
        }
        dfs_solve(to, v);
    }
}
int main(){
    scanf("%d", &n);
    for(int i = 1; i < n; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        addedge(x, y);
        addedge(y, x);
    }
    dfs_dep(1, -1, 1);
    scanf("%d", &q);
    while(q--) {
        int x, d, v;
        scanf("%d%d%d", &x, &d, &v);
        mp[x][min(d, mxdep-dep[x])] += v;
    }
    dfs_solve(1, -1);
    for(int i = 1; i <= n; ++i)
        printf("%lld%c", ans[i], " \n"[i==n]);
    return 0;
}
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details