General

# Author Problem Lang Verdict Time Memory Sent Judged
45608998 Contestant:
kek
1076E - 15 GNU C++14 Hacked 670 ms 25364 KB 2018-11-12 18:10:09 2018-11-12 18:10:14

→ Source
#include <bits/stdc++.h>

//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("fast-math")

#define all(v) v.begin(),v.end()
using namespace std;
#define __int64  long long

const __int64 mod = 1000000007;

__int64 dp[300001];
__int64 res[300001];

vector<pair<int, __int64> > vc[300001];
vector<int> mat[300001];
int lev[300001];

void glev(int v, int l, int p) {
for (auto i:mat[v]) {
if (i == p)
continue;
glev(i, l + 1, v);
}
lev[v] = l;
}

void dfs(int v, int l = 0, int p = -1, __int64 cd = 0) {
for (auto i:vc[v]) {
dp[l + 1 + i.first] -= i.second;
dp[l] += i.second;
}
cd += dp[l];
for (auto i:mat[v]) {
if (i == p)
continue;
dfs(i, l + 1, v, cd);
}
for (auto i:vc[v]) {
dp[l + 1 + i.first] += i.second;
dp[l] -= i.second;
}
res[v] = cd;
}

int main(int argc, char **argv) {

#ifdef DEBUG
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#else
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif
cout << fixed;
cout << setprecision(10);
ios::sync_with_stdio(0);
int n;
cin >> n;
for (int i = 1; i < n; ++i) {
int a, b;
cin >> a >> b;
--a;
--b;
mat[a].push_back(b);
mat[b].push_back(a);
}

glev(0, 0, -1);

int m;
cin >> m;
for (int i = 0; i < m; ++i) {
int v, d;
__int64 x;
cin >> v >> d >> x;
--v;
vc[v].emplace_back(d, x);
}

dfs(0);

for (int i = 0; i < n; ++i) {
cout << res[i] << ' ';
}
return 0;
}


?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
?
?
?