点分治AC#1其他WA求调
查看原帖
点分治AC#1其他WA求调
673867
liu_yi楼主2023/7/24 09:58
#include<bits/stdc++.h>
using namespace std;

int n,m,x,y,z,cnt,head[10010],Q[110],rt,maxn[110],size[10010],a[20010],tot,dis[10000010],sum;
bool t[10010],vis[10010],res[10000010];
struct edge{
	int next,to,dist;
}e[20010];
queue<int>q;
void add(int u,int v,int w){
	e[++cnt].to=v;
	e[cnt].dist=w;
	e[cnt].next=head[u];
	head[u]=cnt;
}
void get_size(int cur,int root){
	size[cur]=1,maxn[cur]=0;
	for(int i=head[cur];i;i=e[i].next){
		int y=e[i].to;
		if(y==root||vis[y])continue;
		get_size(y,cur);
		maxn[cur]=max(maxn[cur],size[y]);
		size[cur]+=size[y];
	}
	maxn[cur]=max(maxn[cur],sum-size[cur]);
	if(!rt||maxn[cur]<maxn[rt])rt=cur;
}
void get_dist(int cur,int root){
	a[++tot]=dis[cur];
	for(int i=head[cur];i;i=e[i].next){
		int y=e[i].to,d=e[i].dist;
		if(y==root||vis[y])continue;
		dis[y]=dis[cur]+d;
		get_dist(y,cur);
	}
}
void calc(int cur,int root){
	t[0]=1,q.push(0),vis[cur]=1;
	for(int i=head[cur];i;i=e[i].next){
		int y=e[i].to,d=e[i].dist;
		if(y==root||vis[y])continue;
		dis[y]=d;
		get_dist(y,cur);
		for(int j=1;j<=tot;j++){
			for(int k=1;k<=m;k++){
				if(Q[k]>=a[j])res[k]|=t[Q[k]-a[j]];
			}
		}
		for(int j=1;j<=cnt;j++)if(a[j]<=1e7)q.push(a[j]),t[a[j]]=1;
		cnt=0;
	}
	while(q.size())t[q.front()]=0,q.pop();
	for(int i=head[cur];i;i=e[i].next){
		int y=e[i].to;
		if(y==root||vis[y])continue;
		sum=size[y];
		maxn[rt=0]=INT_MAX;
		get_size(y,cur);
		get_size(rt,-1);
		calc(rt,cur);
	}
}
inline int read(){
	int step=1,s=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
	    if(ch=='-')step=-1;
	    ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
	    s=(s<<1)+(s<<3)+ch-'0';
	    ch=getchar();
	}
	return step*s;
}
int main(){
	n=read(),m=read();
	for(int i=1;i<n;i++)x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);
	for(int i=1;i<=m;i++)Q[i]=read();
	maxn[0]=n;
	sum=n;
	get_size(1,-1);
	get_size(rt,-1);
	calc(rt,-1);
	for(int i=1;i<=m;i++){
		if(res[i])puts("AYE");
		else puts("NAY");
	}
	return 0;
}
2023/7/24 09:58
加载中...