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);
}

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);
}
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
?
?
?
?