求卡常
  • 板块学术版
  • 楼主shitbro
  • 当前回复6
  • 已保存回复6
  • 发布时间2021/2/2 21:41
  • 上次更新2023/11/5 03:53:52
查看原帖
求卡常
90972
shitbro楼主2021/2/2 21:41
#include <bits/stdc++.h>
#define debug cout<<"YES"<<endl;
using namespace std;
const int N = 1e4 + 5,INF = 1e9 + 5;
struct edge {
	int to,val;
};
vector <edge> V[N];

queue <int> tag;

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

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

bool judge[100000005],res[N],vis[N];
void add_edge(int u,int v,int w) {
	V[u].push_back((edge){v,w});
	V[v].push_back((edge){u,w});
}
void getsize(int u,int fa) {
	siz[u] = 1;
	int maxl = 0;
	for(int i = 0;i < V[u].size();i ++) {	
		int v = V[u][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 = 0;i < V[u].size();i ++) {
		int v = V[u][i].to;
		if(v == fa || vis[v]) continue;
		dis[v] = dis[u] + V[u][i].val;
		getdis(v,u);
	}
}
void dfs(int u,int fa) {
	judge[0] = 1;
	tag.push(0);
	vis[u] = 1;
	for(int i = 0;i < V[u].size();i ++) {
		int v = V[u][i].to;
		if(v == fa || vis[v]) continue;
		dis[v] = V[u][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 = 0;i < V[u].size();i ++) {
		int v = V[u][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:41
加载中...