记录编号	439470	评测结果	WWWWWWWTTW
题目名称	Alone	最终得分	0
用户昵称	wspzz_5	是否通过	未通过
代码语言	C++	运行时间	2.452 s
提交时间	2017-08-20 22:16:31	内存使用	7.95 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int INF=0x7fffffff;
const int MAXN=1e5+20;
vector<int> G[MAXN];
int m;
int val[MAXN],val2[MAXN],size[MAXN],fa[MAXN],n,SEG[MAXN*4],q[MAXN*4],lazytag[MAXN*4],dfn[MAXN];

void build(int o,int L,int R){
	if(L==R) SEG[o]=val[L],q[o]=1;
	else{int mid=(L+R)>>1;
	    build(o*2,L,mid);
	    build(o*2+1,mid+1,R);
	    q[o]=q[o*2]+q[o*2+1];
	}
	//printf("***o=%d   L=%d  R=%d  q=%d   SEG=%d***\n",o,L,R,q[o],SEG[o]);
}

void weihu(int o,int L,int R,int num){
	if(!q[o]) return ;
	if(R<L) return ;
	if(L==R){	
		if(SEG[o]-num<=0){
			q[o]=0;
			}
	//		printf("^^^^o=%d L=%d R=%d q=%d num=%d----  \n",o,L,R,q[o],num);
		return;
	}
	else{
		int mid=(L+R)>>1;
		weihu(o*2,L,mid,num);
		weihu(o*2+1,mid+1,R,num);
		q[o]=q[o*2]+q[o*2+1];
    //	printf("^^^^o=%d L=%d R=%d q=%d  num=%d----  \n",o,L,R,q[o],num);
	}
}

void change(int o,int L,int R,int l,int r,int num){
	//if(!q[o]) return;
	if(R<L) return ;
	else if(L>r||R<l) return ;
	else if(L>=l&&R<=r){
		lazytag[o]+=num;
	//	printf("*  *  *o=%d  q=%d  SEG=%d L=%d  R=%d   lazytag=%d \n",o,q[o],SEG[o],L,R,lazytag[o]);
		weihu(o,L,R,lazytag[o]);
		return ;
	} 
	else{
		int mid=(L+R)>>1;
		if(mid>=l) change(o*2,L,mid,l,r,num);
		if(mid+1<=r) change(o*2+1,mid+1,R,l,r,num);
		q[o]=q[o*2]+q[o*2+1];
	//	printf("***o=%d  q=%d  SEG=%d L=%d  R=%d   lazytag=%d \n",o,q[o],SEG[o],L,R,lazytag[o]);
	}
}

int query(int o,int L,int R,int l,int r){
	if(!q[o]) return 0;
	if(R<L) return 0;
	else if(L>r||R<l) return 0;
	else if(L>=l&&R<=r){
	   // printf("---+--o=%d  q=%d  SEG=%d L=%d  R=%d lazytag=%d \n",o,q[o],SEG[o],L,R,lazytag[o]);
		return q[o];
	}
	else{
		int mid=(L+R)>>1;
		int ans=0;
		if(l<=mid) ans+=query(o*2,L,mid,l,r);
		if(r>=mid+1) ans+=query(o*2+1,mid+1,R,l,r);
		//printf("------o=%d  q=%d  SEG=%d L=%d  R=%d  lazytag=%d \n",o,q[o],SEG[o],L,R,lazytag[o]);
		return ans;
	}
}

int time_;
void dfs(int u,int f){
	dfn[u]=++time_;
	if(G[u].size()==1) return;
	for(int i=0;i<G[u].size();i++){
		int p=G[u][i];
		if(p==f) continue;
		dfs(p,u);
		size[u]+=size[p];
	}
}

void init(){
	scanf("%d",&n);
	size[0]=1;
	for(int i=1;i<=n;i++){
		int f,v;
		scanf("%d%d",&v,&f);
		fa[i]=f;
		G[f].push_back(i);
		G[i].push_back(f);
		val2[i]=v;
		size[i]=1;
	}
	int root=0;
	dfs(root,root);	
	//for(int i=0;i<=n;i++)printf("^^^^%d \n",dfn[i]);
	for(int i=0;i<=n;i++)
        val[dfn[i]]=val2[i];
    val[1]=INF;
//	printf("%d ",dfn[i]);
	build(1,1,size[root]);
	for(int i=1;i<=4*n+4;i++){
		//printf("SEG=%d   q=%d \n",SEG[i],q[i]);
	}
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		int q1;
		scanf("%d",&q1);
		if(!(q1-1)){
			int a,b;
			scanf("%d%d",&a,&b);
			change(1,1,n+1,dfn[a]+1,dfn[a]+size[a]-1,b);
		//	printf("----%d   %d   \n",dfn[a]+1,dfn[a]+size[a]-1);
		}
		else{
			int a;
			scanf("%d",&a);
			printf("%d\n",query(1,1,n+1,dfn[a]+1,dfn[a]+size[a]-1));
		//	printf("***%d   %d   \n",dfn[a]+1,dfn[a]+size[a]-1);
		}
	}
}

int main(){
	freopen("alone.in","r",stdin) ;
	freopen("alone.out","w",stdout);
	init();
	return 0;
}