请求DEBUG
查看原帖
请求DEBUG
922691
Hisy楼主2024/7/4 15:00
#include<cstdio>
struct node{
	int from,dist,next;
};
int dots,action,sum,root,answer;
int top=0,head[100001],maxp[100001],size[100001],dist[100001],rems[100001],query[1001];
bool visit[100001],test[10000001],judge[10000001],queue[100001];
node edge[100001];
inline int max(int first,int second){
	if(first>second){
		return first;
	};
	return second;
};
inline void addedge(int to,int from,int dist){
	edge[++top].next=head[from];
	edge[top].from=from;
	edge[top].dist=dist;
	head[from]=top;
	return;
};
inline void getroot(int to,int parent){
	size[to]=1;
	maxp[to]=0;
	for(int iter=head[to];iter;iter=edge[iter].next){
		int from=edge[iter].from;
		if(from==parent||visit[from]){
			continue;
		};
		getroot(from,to);
		size[to]+=size[from];
		maxp[to]=max(maxp[to],size[from]);
	};
	maxp[to]=max(maxp[to],sum-size[to]);
	if(maxp[to]<maxp[root]){
		root=to;
	};
	return;
};
inline void getdist(int to,int parent){
	rems[++rems[0]]=dist[to];
	for(int iter=head[to];iter;iter=edge[iter].next){
		int from=edge[iter].from;
		if(from==parent||visit[from]){
			continue;
		};
		dist[from]=dist[to]+edge[iter].dist;
		getdist(from,to);
	};
	return;
};
inline void clac(int to){
	int top=0;
	for(int first=head[to];first;first=edge[first].next){
		int from=edge[first].from;
		if(visit[from]){
			continue;
		};
		rems[0]=0;
		dist[from]=edge[first].dist;
		getdist(from,to);
		for(int second=rems[0];second;--second){
			for(int third=1;third<=action;++third){
				if(query[third]>=rems[second]){
					test[third]|=judge[query[third]-rems[second]];
				};
			};
		};
		for(int second=rems[0];second;--second){
			queue[++top]=rems[second];
			judge[rems[second]]=true;
		};
	};
	for(int iter=1;iter<=top;++iter){
		judge[queue[iter]]=false;
	};
	return;
};
inline void solve(int to){
	judge[0]=visit[to]=true;
	clac(to);
	for(int iter=head[to];iter;iter=edge[iter].next){
		int from=edge[iter].from;
		if(visit[from]){
			continue;
		};
		sum=size[from];
		maxp[root=0]=10000001;
		getroot(from,0);
		solve(root);
	};
	return;
};
int main(int argc,char **argv){
	scanf("%d %d",&dots,&action);
	for(int iter=1;iter<dots;++iter){
		int from,to,dist;
		scanf("%d %d %d",&from,&to,&dist);
		addedge(from,to,dist);
		addedge(to,from,dist);
	};
	for(int iter=1;iter<=action;++iter){
		scanf("%d",&query[iter]);
	};
	maxp[root]=sum=dots;
	getroot(1,0);
	solve(root);
	for(int iter=1;iter<=action;++iter){
		if(test[iter]){
			puts("AYE");
		}else{
			puts("NAY");
		};
	};
	return 0;
};
2024/7/4 15:00
加载中...