记录编号	252753	评测结果	AAAAAAAAA
题目名称	[JLOI 2015] 城池攻占	最终得分	100
用户昵称	zys	是否通过	通过
代码语言	C++	运行时间	3.140 s
提交时间	2016-04-20 21:03:25	内存使用	23.47 MiB

#define MAXN 300010UL
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long

using namespace std;

bool typ[MAXN];
ll def[MAXN], v[MAXN], atk[MAXN], add[MAXN], mul[MAXN];
int n, m, t, d[MAXN], dep[MAXN], tot, die[MAXN], l[MAXN], r[MAXN], Rt[MAXN], Ans[MAXN], ans_add[MAXN];

struct Edge {
	int hou, nt;
}sg[MAXN];

void Insert(int x, int y) {
	sg[t] = (Edge){y, d[x]}, d[x] = t ++;
	return;
}

void Push_down(int x) {
	if(mul[x]!=1ll) {
		mul[l[x]] *= mul[x], mul[r[x]] *= mul[x];
		add[l[x]] *= mul[x], add[r[x]] *= mul[x];
		atk[l[x]] *= mul[x], atk[r[x]] *= mul[x];
		mul[x] = 1ll;
	}
	if(add[x]) {
		add[l[x]] += add[x], add[r[x]] += add[x];
		atk[l[x]] += add[x], atk[r[x]] += add[x];
		add[x] = 0;
	}
	if(ans_add[x]) {
		Ans[l[x]] += ans_add[x], Ans[r[x]] += ans_add[x];
		ans_add[l[x]] += ans_add[x], ans_add[r[x]] += ans_add[x];
		ans_add[x] = 0;
	}
	return;
}

int Merge(int x, int y) {
	if((!x)||(!y)) return x+y;
	if(atk[x]>atk[y]) swap(x, y);
	Push_down(x);
	r[x] = Merge(r[x], y);
	if(dep[l[x]]<dep[r[x]]) swap(l[x], r[x]);
	dep[x] = dep[r[x]]+1;
	return x;
}

void Pop(int x) {
	Push_down(Rt[x]);
	Rt[x] = Merge(l[Rt[x]], r[Rt[x]]);
	return;
}

void Dfs(int x) {
	for(int i = d[x] ; i != -1 ; i = sg[i].nt) {
		Dfs(sg[i].hou);
		Rt[x] = Merge(Rt[x], Rt[sg[i].hou]);
	}
	while(atk[Rt[x]]<def[x]&&Rt[x]) Pop(x), ++ die[x];
	if(Rt[x]) {
		int cur = Rt[x];
		if(!typ[x]) atk[cur] += v[x], add[cur] += v[x];
		else atk[cur] *= v[x], mul[cur] *= v[x], add[cur] *= v[x];
		++ Ans[cur], ++ ans_add[cur];
	}
	return;
}

void Push_mark(int x) {
	if(!x) return;
	Push_down(x);
	if(l[x]) Push_mark(l[x]);
	if(r[x]) Push_mark(r[x]);
	return;
}

int main() {
	freopen("fall.in", "r", stdin);
	freopen("fall.out", "w", stdout);
	int size = 40 << 20;
	char *p = (char*)malloc(size) + size;
	__asm__("movl %0, %%esp\n" :: "r"(p));
	memset(d, -1, sizeof(d));
	dep[0] = -1;
	scanf("%d%d", &n, &m);
	for(int i = 1 ; i <= n ; ++ i) scanf("%lld", &def[i]);
	for(int i = 2, x ; i <= n ; ++ i) {
		scanf("%d%d%lld", &x, &typ[i], &v[i]);
		Insert(x, i);
	}
	for(int i = 1, c ; i <= m ; ++ i) {
		mul[i] = 1ll;
		scanf("%lld%d", &atk[i], &c);
		if(!Rt[c]) Rt[c] = i;
		else Rt[c] = Merge(Rt[c], i);
	}
	Dfs(1);
	Push_mark(Rt[1]);
	for(int i = 1 ; i <= n ; ++ i) printf("%d\n", die[i]);
	for(int i = 1 ; i <= m ; ++ i) printf("%d\n", Ans[i]);
	//while(1);
	return 0;
}