POJ2114 点分治的题，卡不过去了。

#include <cstdio>
#include <bitset>
#include <vector>
using namespace std;
const int N=10005,M=105;
int siz[N],dep[N],Min,Minn,cnt[N],vis[N],n,m,u,v,w,qry[M];
struct edge {
	int to,w;
}lxl;
vector<edge> G[N];
bool ans[M];
bool bit[10000005];
void dfs(int p,int lst,int Sz) {
	siz[p]=1;
	int tmp=0;
	for(int i=0,Siz=G[p].size();i!=Siz;i++) {
		lxl=G[p][i];
		if(lxl.to!=lst&&!vis[lxl.to]) {
			dfs(lxl.to,p,Sz);
			siz[p]+=siz[lxl.to];
			tmp=max(tmp,siz[lxl.to]);
		}
	} 
	if(Min>max(tmp,Sz-siz[p])) Min=max(tmp,Sz-siz[p]),Minn=p;
}
void deal(int p,int lst) {
	for(int i=0,Siz=G[p].size();i!=Siz;i++) {
		lxl=G[p][i];
		if(lxl.to!=lst&&!vis[lxl.to]) {
			dep[lxl.to]=dep[p]+lxl.w;
			deal(lxl.to,p);
		}
	}
	for(int i=1;i<=m;i++) {
		if(qry[i]>=dep[p]&&bit[qry[i]-dep[p]]) 
			ans[i]=1; 
	}
}
void calc(int p,int lst) {
	for(int i=0,Siz=G[p].size();i!=Siz;i++) {
		lxl=G[p][i];
		if(lxl.to!=lst&&!vis[lxl.to]) 
			calc(lxl.to,p);
	}
	bit[dep[p]]=1;
}
void clear(int p,int lst) {
	for(int i=0,Siz=G[p].size();i!=Siz;i++) {
		lxl=G[p][i];
		if(lxl.to!=lst&&!vis[lxl.to]) 
			clear(lxl.to,p);
	}
	bit[dep[p]]=0;
	dep[p]=0;
}
void solve(int p,int Sz) {
	Min=0x7f7f7f7f;
	Minn=0;
	dfs(p,0,Sz);
	p=Minn;
	bit[0]=1;
	for(int i=0,Siz=G[p].size();i!=Siz;i++) {
		lxl=G[p][i];
		if(!vis[lxl.to]) {
			dep[lxl.to]=lxl.w;
			deal(lxl.to,p),calc(lxl.to,p);
		}
	}
	clear(p,0);
	vis[p]=1;
	for(int i=0,Siz=G[p].size();i!=Siz;i++) {
		lxl=G[p][i];
		if(!vis[lxl.to]) 
			solve(lxl.to,siz[lxl.to]);
	}
}
int main() {
//	freopen("data.in","r",stdin);
//	freopen("data.out","w",stdout);
	while(1) {
		for(int i=1;i<=n;i++) G[i].clear(),vis[i]=0;
		for(int i=1;i<=m;i++) ans[i]=0;
		scanf("%d",&n);
		if(n==0) break;
		for(int i=1;i<=n;i++) {
			int x,y;
			while(1) {
				scanf("%d",&x);
				if(x==0) break;
				scanf("%d",&y);
				G[i].push_back((edge){x,y});
				G[x].push_back((edge){i,y});
			}
		}
		m=0;
		while(1) {
			scanf("%d",&qry[++m]);
			if(qry[m]==0) {
				m--;
				break;
			}
		}
		solve(1,0);
		for(int i=1;i<=m;i++) {
			if(ans[i]) puts("AYE");
			else puts("NAY");
		}
		puts(".");
	}
	return 0;
}