记录编号	469075	评测结果	AAAAAAAAA
题目名称	[JLOI 2015] 城池攻占	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	2.464 s
提交时间	2017-11-02 17:43:09	内存使用	17.77 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long L;
inline L read(){
	L sum(0),f(1);char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum*f;
}
#define get_dis(x) (x?x->dis:-1)
struct node{
	node *lch,*rch;
	L key,add,mul;
	int id,dis;
	node(L v=0,int x=0):lch(NULL),rch(NULL),key(v),add(0),mul(1),id(x),dis(0){}
	inline void pushdown(){
		if(add||mul^1){
			if(this->lch){
				this->lch->key=this->lch->key*this->mul+this->add;
				this->lch->add=this->lch->add*this->mul+this->add;
				this->lch->mul*=this->mul;
			}
			if(this->rch){
				this->rch->key=this->rch->key*this->mul+this->add;
				this->rch->add=this->rch->add*this->mul+this->add;
				this->rch->mul*=this->mul;
			}
			this->add=0;this->mul=1;
		}
	}
	inline void fixdis(){
		if(get_dis(this->lch)<get_dis(this->rch))
			swap(this->lch,this->rch);
		this->dis=get_dis(this->rch)+1;
	}
}*heap[300005];
struct edge{
	int e;
	edge *n;
}*pre[300005];
inline void insert(int s,int e){
	edge *tmp(new edge);
	tmp->e=e;tmp->n=pre[s];pre[s]=tmp;
}
int n,m,dep[300005],fa[300005],c[300005],kill[300005],att[300005],du[300005];
int que[300005],head,tail;
L h[300005],a[300005],v[300005];
bool vis[300005];
inline node* merge(node *&x,node *&y){
	if(!x)return y;if(!y)return x;//cout<<x<<' '<<x->rch<<' '<<y<<endl;
	if(x->key>y->key)swap(x,y);
	x->pushdown();x->rch=merge(x->rch,y);x->fixdis();return x;
}
inline void insert(node *&x,L v,int id){
	node *tmp(new node(v,id));
	x=merge(x,tmp);
}
inline node* pop(node *&x){
	if(!x)return NULL;x->pushdown();
	return merge(x->lch,x->rch);
}
inline void add(node *&x,L v){
	if(!x)return;
	x->pushdown();
	x->add+=v;
	x->key+=v;
}
inline void mul(node *&x,L v){
	if(!x)return;
	x->pushdown();
	x->mul*=v;
	x->key*=v;
}
int main(){
	freopen("fall.in","r",stdin);freopen("fall.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;++i)
		h[i]=read();
	for(int i=2;i<=n;++i)
		fa[i]=read(),a[i]=read(),v[i]=read(),insert(fa[i],i),++du[fa[i]];
	que[++tail]=1;dep[1]=1;
	while(head<tail){
		int k(que[++head]);
		for(edge *i=pre[k];i;i=i->n){
			dep[i->e]=dep[k]+1;
			que[++tail]=i->e;
		}
	}
	for(int i=1;i<=m;++i){
		L x(read());c[i]=read();
		insert(heap[c[i]],x,i);
	}
	for(int k=n;k>=1;--k){
		while(heap[k]&&h[k]>heap[k]->key){
			++kill[k];
			att[heap[k]->id]=dep[c[heap[k]->id]]-dep[k];
			heap[k]=pop(heap[k]);
		}
		if(heap[k]){
			if(a[k]==0)
				add(heap[k],v[k]);
			else
				mul(heap[k],v[k]);
		}
		if(fa[k]){
			heap[fa[k]]=merge(heap[fa[k]],heap[k]);
			if(!vis[fa[k]]){
				vis[fa[k]]=1;
				que[++tail]=fa[k];
			}
		}
	}
	while(heap[1]){
		att[heap[1]->id]=dep[c[heap[1]->id]];
		heap[1]=pop(heap[1]);
	}
	for(int i=1;i<=n;++i)printf("%d\n",kill[i]);
	for(int i=1;i<=m;++i)printf("%d\n",att[i]);
}