求助关于淀粉质
查看原帖
求助关于淀粉质
704234
Sad_Rex楼主2023/7/24 14:04
#include<bits/stdc++.h>
//#pragma GCC optimize(3, "Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
using namespace std;
#define int long long
#define kg putchar(' ')
#define endl puts("")
inline int read(){
    int vis=1,ans=0;
    char x=getchar();
    while(x<'0'||x>'9'){
        if(x=='-')vis=-1;
        x=getchar();
    }
    while(x>='0'&&x<='9'){
        ans=ans*10+x-'0';
        x=getchar();
    }
    return vis*ans;
}
inline void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
int n=read(),m=read();
const int N=1e4+9,M=1e8+9;
int u,v,w;
int minn=LONG_LONG_MAX;
struct node{
	int nxt,to,w;
}e[2*N];
int head[N],cnt;
inline void add(int x,int y,int w){
	++cnt;
	e[cnt].to=y;
	e[cnt].nxt=head[x];
	e[cnt].w=w;
	head[x]=cnt;
}
int root,size[N],maxnson[N];
bool vis[N];
int tmp=0,dis[N];
int Sumnode;
int num[M];
inline void get_heavy(int p,int fa){
	size[p]=1,maxnson[p]=0;
	for(int i=head[p];i;i=e[i].nxt){
		int y=e[i].to;
		if(vis[y]||y==fa)continue;
		get_heavy(y,p);
		size[p]+=size[y];
		maxnson[p]=max(maxnson[p],size[y]);
	}
	maxnson[p]=max(maxnson[p],Sumnode-size[p]);
	if(maxnson[p]<minn)minn=maxnson[p],root=p;
}
inline void ask(int begin,int fa,int len){
	dis[++tmp]=len;
	for(int i=head[begin];i;i=e[i].nxt){
		int y=e[i].to;
		if(vis[y]||y==fa)continue;
		ask(y,begin,len+e[i].w);
	}
}
inline void init(int p,int len,bool f){
	tmp=0;
	ask(p,0,len);
	if(f==1){
		for(int i=1;i<tmp;i++){
			for(int j=i+1;j<=tmp;j++){
				num[dis[i]+dis[j]]++;
			}
		}
	}else if(f==0){
		for(int i=1;i<tmp;i++){
			for(int j=i+1;j<=tmp;j++){
				num[dis[i]+dis[j]]--;
			}
		}
	}
}
inline void difen(int p){
	vis[p]=1;
	init(p,0,1);
	for(int i=head[p];i;i=e[i].nxt){
		int y=e[p].to;
		if(vis[y])continue;
		init(y,e[i].w,0);
		minn=LONG_LONG_MAX,root=0,Sumnode=size[y];
		get_heavy(y,0);
		difen(root);
	}
}
signed main(){
//	freopen(".in","r",stdin);
//	freopen("SB.out","w",stdout);
	Sumnode=n;
	for(int i=1;i<n;i++){
		u=read(),v=read(),w=read();
		add(u,v,w),add(v,u,w);
	}
	get_heavy(1,0);
	difen(root);
	while(m--){
		int k=read();
		if(num[k])puts("AYE");
		else puts("NAY");
	}
    return 0;
}
/*
2 1
1 2 2
2
*/
2023/7/24 14:04
加载中...