REon 6,9,10
查看原帖
REon 6,9,10
800499
suzhikz楼主2024/5/21 19:42
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> g[100005],w[100005]; 
int root,minn=1e9;
int siz[100005],maxx[100005],vis[100005];
int summ;
void dfs(int x,int fa){
	siz[x]=1;
	maxx[x]=0;
	for(int i=0;i<g[x].size();i++){
		int v=g[x][i];
		if(v==fa||vis[v])continue;
		dfs(v,x);
		siz[x]+=siz[v];
		maxx[x]=max(maxx[x],siz[v]);
	}
	maxx[x]=max(maxx[x],summ-siz[x]);
	if(maxx[x]<maxx[root]||!root) {//0
		root=x;
	}
}
struct node{
	int id,q,ok;
}z[105];
struct abc{
	int de,be;
}k[100005];
int tot;
bool cmp(abc a,abc b){
	return a.de<b.de;
}
void get_dis(int x,int fa,int dis,int belong_){
	k[++tot].de=dis;
	k[tot].be=belong_;
	for(int i=0;i<g[x].size();i++){
		int v=g[x][i];
		if(v==fa||vis[v])continue;
		get_dis(v,x,dis+w[x][i],belong_);
	}
}
void calc(int x){
	tot=0;
	k[++tot].de=0;
	k[tot].be=0;
	for(int i=0;i<g[x].size();i++){
		int v=g[x][i];
		if(vis[v])continue;
		get_dis(v,x,w[x][i],v);
	}
	sort(k+1,k+1+tot,cmp);
	for(int i=1;i<=m;i++){
		int l=1,r=tot;
		if(z[i].ok)continue;
		while(l<r){
			//cout<<k[l].de+k[r].de<<endl;
			if(k[l].de+k[r].de<z[i].q){
				l++;
			}else if(k[l].de+k[r].de>z[i].q){
				r--;
			}else if(k[l].be==k[r].be){
				if(k[l].de==k[l+1].de)l++;
				else r--;
			}else{
				z[i].ok=1;
				break;
			}
		}
	}
}
void solve(int x){
	vis[x]=1;
	calc(x);
	for(int i=0;i<g[x][i];i++){
		if(vis[g[x][i]])continue;
		int v=g[x][i];
		root=0;
		summ=siz[v];
		dfs(v,x);
		solve(root);
	}
}
int main(){
	cin>>n>>m;
	for(int i=1,u,v,c;i<n;i++){
		cin>>u>>v>>c;
		g[u].push_back(v);
		g[v].push_back(u);
		w[u].push_back(c);
		w[v].push_back(c);
	}
	for(int i=1;i<=m;i++){
		z[i].id=i;
		cin>>z[i].q;
	}
	root=0;
	maxx[root]=n;
	dfs(1,0);
	solve(root);
	for(int i=1;i<=m;i++){
		if(z[i].ok)puts("AYE");
		else puts("NAY");
	}
	return 0;
}

2024/5/21 19:42
加载中...