oi-wiki的写法

#include <iostream>
#include <vector>
using namespace std;
const int N = 10005, K = 10000005, inf = 1e9;
struct Edge{
	int e, to, nxt;
}g[N << 1];
int h[N], idx;
bool ans[N], st[N];
int vis[K], Time;
int siz[N], mx[N], dist[N], sum, root;
int dis[N], tot;
int q[N], n, m;
void add(int a,int b,int c)
{
	g[++idx] = {c, b, h[a]}, h[a] = idx;
}
void dfs_size(int u,int fa)
{
	siz[u] = 1;
	mx[u] = 0;
	for (int i = h[u]; i; i = g[i].nxt)
	{
		int j = g[i].to;
		if (j == fa || st[j])
			continue;
		dfs_size(j, u);
		mx[u] = max(mx[u], siz[j]);
		siz[u] += siz[j];
	}
	mx[u] = max(mx[u], sum - siz[u]);
	if (mx[u] < mx[root])
		root = u;
}
void dfs_dist(int u,int fa)
{
	dis[++ tot] = dist[u];
	for (int i = h[u]; i; i = g[i].nxt)
	{
		int j = g[i].to;
		if (j == fa || st[j])
			continue;
		dist[j] = dist[u] + g[i].e;
		if (dist[j] <= 10000000)
			dfs_dist(j, u);
	}
}
void dfs(int u,int fa)
{
	vis[0] = ++ Time;
	st[u] = true;
	for (int i = h[u]; i; i = g[i].nxt)
	{
		int j = g[i].to;
		if (j == fa || st[j])
			continue;
		tot = 0;
		dist[j] = g[i].e;
		dfs_dist(j, u);
		for (int d=1;d<=tot;d++)
			for (int k=1;k<=m;k++)
				if (dis[d] <= q[k])
					ans[k] |= vis[q[k] - dis[d]] == Time;
		for (int d=1;d<=tot;d++)
			vis[dis[d]] = Time;
	}
	for (int i = h[u]; i; i = g[i].nxt)
	{
		int j = g[i].to;
		if (j == fa || st[j])
			continue;
		sum = siz[j];
		root = 0;
		mx[root] = inf;
		dfs_size(j, u);
		dfs_size(root, root);
		dfs(j, u);
	}
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i=1;i<n;i++)
	{
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		add(a, b, c);
		add(b, a, c);
	}
	for (int i=1;i<=m;i++)
		scanf("%d", &q[i]);
	mx[root] = inf;
	sum = n;
	dfs_size(1, 1);
	dfs_size(root, root);
	dfs(root, root);
	for (int i=1;i<=m;i++)
		if (ans[i])
			puts("AYE");
		else
			puts("NAY");
	return 0;
}