Submission #19723579


Source Code Expand

Copy
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <stack>
#include <queue>
#include <array>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <random>
#include <chrono>
#include <utility>
#include <numeric>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <sstream>
#include <assert.h>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(bool x) {cerr << (x ? "true" : "false");}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}

template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";}
template <typename T, typename... V>void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef HOME
#warning CHECK int:ll::INT_MAX:LLONG_MAX
#define maxn 20
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define maxn 2000006
#define gcd __gcd
#define debug(x...)
#endif

#define ff first
#define endl '\n'
#define ss second
#define inf 0x3f3f3f3f
#define MOD 1000000007
#define PI 3.14159265358979323846264338327950L
#define f(i,x,n) for(int i=x;i<=n;i++)
#define fr(i,x,n) for(int i=x;i>=n;i--)
struct _ { ios_base::Init i; _() { ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL); } } _;

int dx[] = { -1, 0, 1, 0, -1, -1, 1, 1};
int dy[] = {0, 1, 0, -1, -1, 1, 1, -1};


int main() {

	long long n; cin >> n;
	vector<long long> a(n), b(n);
	vector<vector<long long>> gr(n + 1);

	for (long long i = 1; i <= n - 1; i++) {
		cin >> a[i] >> b[i];
		gr[a[i]].push_back(b[i]);
		gr[b[i]].push_back(a[i]);
	}

	vector<long long> dp(n + 1, 0), lvl(n + 1, 0);

	function<void(long long, long long)> dfs = [&](long long curr, long long par) -> void {
		lvl[curr] = lvl[par] + 1;
		for (auto child : gr[curr]) {
			if (child == par) continue;
			dfs(child, curr);
		}
	};

	dfs(1, 1);

	long long q; cin >> q;
	while (q--) {
		long long t, e, x; cin >> t >> e >> x;

		if (t == 1) {
			if (lvl[a[e]] < lvl[b[e]]) dp[1] += x, dp[b[e]] -= x;
			else dp[a[e]] += x;
		}
		else {
			if (lvl[b[e]] <= lvl[a[e]]) dp[1] += x, dp[a[e]] -= x;
			else dp[b[e]] += x;
		}
	}

	function<void(long long, long long)> push = [&](long long curr, long long par) -> void{
		for (auto child : gr[curr]) {
			if (child == par) continue;
			dp[child] += dp[curr];
			push(child, curr);
		}
	};

	push(1, 1);

	for (long long i = 1; i <= n; i++) cout << dp[i] << "\n";

	return 0;
}

Submission Info

Submission Time
Task E - Through Path
User Ausmosian
Language C++ (Clang 10.0.0)
Score 500
Code Size 3325 Byte
Status AC
Exec Time 737 ms
Memory 34620 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 36
Set Name Test Cases
Sample 01_sample.txt, 02_sample.txt, 03_sample.txt
All 01_sample.txt, 02_sample.txt, 03_sample.txt, 04_small.txt, 05_small.txt, 06_small.txt, 07_small.txt, 08_small.txt, 09_small.txt, 10_small.txt, 11_small.txt, 12_small.txt, 13_small.txt, 14_small.txt, 15_small.txt, 16_small.txt, 17_small.txt, 18_small.txt, 19_small.txt, 20_small.txt, 21_small.txt, 22_small.txt, 23_small.txt, 24_large.txt, 25_large.txt, 26_large.txt, 27_max.txt, 28_max.txt, 29_max.txt, 30_path.txt, 31_path.txt, 32_path.txt, 33_star.txt, 34_star.txt, 35_star.txt, 36_star.txt
Case Name Status Exec Time Memory
01_sample.txt AC 6 ms 3156 KB
02_sample.txt AC 3 ms 3128 KB
03_sample.txt AC 2 ms 3080 KB
04_small.txt AC 10 ms 3076 KB
05_small.txt AC 4 ms 3004 KB
06_small.txt AC 2 ms 3004 KB
07_small.txt AC 3 ms 3040 KB
08_small.txt AC 2 ms 3100 KB
09_small.txt AC 5 ms 3128 KB
10_small.txt AC 4 ms 3144 KB
11_small.txt AC 2 ms 3044 KB
12_small.txt AC 4 ms 3168 KB
13_small.txt AC 4 ms 3168 KB
14_small.txt AC 4 ms 3120 KB
15_small.txt AC 4 ms 3140 KB
16_small.txt AC 3 ms 3124 KB
17_small.txt AC 3 ms 3076 KB
18_small.txt AC 5 ms 3096 KB
19_small.txt AC 6 ms 3104 KB
20_small.txt AC 4 ms 3144 KB
21_small.txt AC 3 ms 3132 KB
22_small.txt AC 4 ms 3144 KB
23_small.txt AC 3 ms 3132 KB
24_large.txt AC 582 ms 19332 KB
25_large.txt AC 521 ms 16968 KB
26_large.txt AC 213 ms 6592 KB
27_max.txt AC 718 ms 21800 KB
28_max.txt AC 706 ms 21784 KB
29_max.txt AC 695 ms 22036 KB
30_path.txt AC 737 ms 28712 KB
31_path.txt AC 733 ms 34620 KB
32_path.txt AC 717 ms 27608 KB
33_star.txt AC 637 ms 22168 KB
34_star.txt AC 689 ms 21788 KB
35_star.txt AC 643 ms 22064 KB
36_star.txt AC 655 ms 22104 KB