fork(1) download 
#include <bits/stdc++.h>

#define pb push_back
#define f first
#define s second
#define mp make_pair
#define sz(a) int((a).size())
#ifdef _WIN32
#  define I64 "%I64d"
#else
#  define I64 "%lld"
#endif
#define fname "."
#define pi pair < int, int >
#define pp pop_back

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int MAX_N = (int)5e5 + 123;
const double eps = 1e-6;
const int inf = (int)1e9 + 123;

using namespace std;

int n, m, q;
vector < int > g[MAX_N];
vector < int > own[MAX_N];
ll need[MAX_N];

struct tree {
	ll add;
	int l, r;
	tree() : add(0), l(-1), r(-1) {}
};

vector < tree > t, t2;

int update(int l, int r, ll x, int v, int tl = 1, int tr = n) {
	if (tl > r || l > tr)
		return v;
	int now = sz(t);
	t.pb(tree());
	if (v != -1)
		t[now] = t[v];
	if (tl >= l && tr <= r) {
		t[now].add += x;
		return now;
	}
	int tm = (tl + tr) / 2;
	int hey = update(l, r, x, (v == -1 ? -1 : t[v].l), tl, tm);
	t[now].l = hey;
	hey = update(l, r, x, (v == -1 ? -1 : t[v].r), tm + 1, tr);
	t[now].r = hey;
	return now;
}

ll get(int x, int v, int tl = 1, int tr = n) {
	if (v == -1)
		return 0;
	if (tl == tr)
		return t[v].add;
	int tm = (tl + tr) / 2;
	if (x <= tm)
		return t[v].add + get(x, t[v].l, tl, tm);
	return t[v].add + get(x, t[v].r, tm + 1, tr);
}

int update2(int l, int r, ll x, int v, int tl = 1, int tr = n) {
	if (tl > r || l > tr)
		return v;
	int now = sz(t2);
	t2.pb(tree());
	if (v != -1)
		t2[now] = t2[v];
	if (tl >= l && tr <= r) {
		t2[now].add += x;
		return now;
	}
	
	int tm = (tl + tr) / 2;
	
// -----
	int hey = update2(l, r, x, (v == -1 ? -1 : t2[v].l), tl, tm);
	t2[now].l = hey;
	hey = update2(l, r, x, (v == -1 ? -1 : t2[v].r), tm + 1, tr);
	t2[now].r = hey;
// -----


/*	t2[now].l = update2(l, r, x, (v == -1 ? -1 : t2[v].l), tl, tm);
	t2[now].r = update2(l, r, x, (v == -1 ? -1 : t2[v].r), tm + 1, tr);*/
	
	return now;
}

ll get2(int x, int v, int tl = 1, int tr = n) {
	if (v == -1)
		return 0;
	if (tl == tr)
		return t2[v].add;
	int tm = (tl + tr) / 2;
	if (x <= tm)
		return t2[v].add + get2(x, t2[v].l, tl, tm);
	return t2[v].add + get2(x, t2[v].r, tm + 1, tr);
}

pi root[MAX_N];
int L[MAX_N], R[MAX_N], timer;
int lvl[MAX_N];

void dfs(int v, int pr = 0) {
	lvl[v] = lvl[pr] + 1;
	L[v] = ++timer;
	for (auto to : g[v])
		dfs(to, v);
	R[v] = timer;
}

bool check(int id, int x) {
	ll res = 0;
	for (auto i : own[x])
		res += 1ll * lvl[i] * get(L[i], root[id].f) + get2(L[i], root[id].s);
	return (res >= need[x]);
}

int Find(int x) {
	int l = 1, r = q, mid = -1, ans = -1;
	while(l <= r) {
		mid = (l + r) / 2;
		if (check(mid, x))
			ans = mid, r = mid - 1;
		else
			l = mid + 1;
	}
	return ans;
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 2, x; i <= n; i++) {
		scanf("%d", &x);
		g[x].pb(i);
	}
	for (int i = 1, x; i <= n; i++) {
		scanf("%d", &x);
		own[x].pb(i);
	}
	for (int i = 1; i <= m; i++)
		scanf(I64, &need[i]);
	dfs(1);
	scanf("%d", &q);
	for (int i = 1, v, x, d; i <= q; i++) {
	  scanf("%d%d%d", &v, &x, &d);
		int last = (i == 1 ? -1 : root[i - 1].f);
		root[i].f = update(L[v], R[v], d, last);

		last = (i == 1 ? -1 : root[i - 1].s);
		ll now = 0ll - 1ll * lvl[v] * d + x;
		root[i].s = update2(L[v], R[v], now, last);
	}
	for (int i = 1; i <= m; i++) {
		int ans = Find(i);
		if (ans == -1)
			printf("rekt\n");
		else
			printf("%d\n", ans);
	}
	return 0;
}
Success #stdin #stdout 0.02s 28864KB
comments (?)
stdin 
3 3
1 2
1 2 3
10 15 20
5
1 2 3
2 2 3
3 5 10
1 4 0
1 3 3
stdout 
rekt
5
4
https://ideone.com/QxhGT6
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!