#8#9tle了?
查看原帖
#8#9tle了?
90972
shitbro楼主2021/2/2 21:49
#include <bits/stdc++.h>
#define debug cout<<"YES"<<endl;
using namespace std;
const int N = 1e4 + 5,INF = 1e9 + 5;
queue <int> tag;

int n,m,sum,MAX,root,cnt,tot;

int siz[N],dis[N],q[N],dd[N],head[N];

bool judge[100000005],res[N],vis[N];

struct edge {
	int to,nxt,val;
}e[N << 1];
void add_edge(int u,int v,int w) {
	e[++ tot].nxt = head[u];
	e[tot].to = v;
	e[tot].val = w;
	head[u] = tot;
	e[++ tot].nxt = head[v];
	e[tot].to = u;
	e[tot].val = w;
	head[v] = tot;
}
void getsize(int u,int fa) {
	siz[u] = 1;
	int maxl = 0;
	for(int i = head[u];i;i = e[i].nxt) {	
		int v = e[i].to;
		if(v == fa || vis[v]) continue;
		getsize(v,u);
		siz[u] += siz[v];
		maxl = max(maxl,siz[u]);
	}
	maxl = max(maxl,sum - siz[u]);
	if(maxl < MAX) {
		MAX = maxl;
		root = u;
	}
}
void getdis(int u,int fa) {
	dd[++ cnt] = dis[u];
	for(int i = head[u];i;i = e[i].nxt) {
		int v = e[i].to;
		if(v == fa || vis[v]) continue;
		dis[v] = dis[u] + e[i].val;
		getdis(v,u);
	}
}
void dfs(int u,int fa) {
	judge[0] = 1;
	tag.push(0);
	vis[u] = 1;
	for(int i = head[u];i;i = e[i].nxt) {
		int v = e[i].to;
		if(v == fa || vis[v]) continue;
		dis[v] = e[i].val;
		getdis(v,u);
		for(int j = 1;j <= cnt;j ++) {
			for(int k = 1;k <= m;k ++) {
				if(q[k] - dd[j] >= 0) {
					res[k] |= judge[q[k] - dd[j]];
				}
			}
		}
		for(int j = 1;j <= cnt;j ++) {
			tag.push(dd[j]);
			judge[dd[j]] = 1;
		}
		cnt = 0;
	}
	while(!tag.empty()) {
		judge[tag.front()] = 0;
		tag.pop();
	}
	for(int i = head[u];i;i = e[i].nxt) {
		int v = e[i].to;
		if(v == fa || vis[v]) continue;
		sum = siz[v];
		root = 0;
		MAX = INF;
		getsize(v,u);
		getsize(root,0);
		dfs(root,u);
	}
}
int main() {
	scanf("%d%d",&n,&m);
	for(int i = 1;i < n;i ++) {
		int u,v,w; scanf("%d%d%d",&u,&v,&w);
		add_edge(u,v,w);
	}
	for(int i = 1;i <= m;i ++) {
		scanf("%d",&q[i]);
	}
	root = 0;
	MAX = INF;
	sum = n;
	getsize(1,0);
	getsize(root,0);
	dfs(root,0);
	for(int i = 1;i <= m;i ++) {
		if(res[i]) puts("AYE");
		else puts("NAY");
	}
	return 0;
}


2021/2/2 21:49
加载中...