P3806 点分治1 求条

WA #1

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6 + 10;
ll n, m; 
vector <ll> v[N];
vector <ll> w[N];
ll q[N], t[N];
ll maxn[N], sum, rt;
ll siz[N], rem[N], dis[N];
bool vis[N], test[N], judge[N];
void get_rt (ll u, ll fa) {
	siz[u] = 1, maxn[u] = 0;
	ll sz = v[u].size ();
	for (int i = 0; i < sz; ++ i) {
		ll y = v[u][i];
		if (y == fa || vis[y]) {
			continue;
		}
		get_rt (y, u);
		siz[u] += siz[y];
		maxn[u] = max (maxn[u], siz[y]);
	}
	maxn[u] = max (maxn[u], sum - siz[u]);
	if (maxn[u] < maxn[rt]) {
		rt = u;
	}
}
void get_dis (ll u, ll fa) {
	rem[++rem[0]] = dis[u];
	ll sz = v[u].size ();
	for (int i = 0; i < sz; ++ i) {
		ll y= v[u][i];
		if (y == fa || vis[y]) {
			continue;
		}
		dis[y] = dis[u] + w[u][i];
		get_dis (y, u); 
	}
}
void dfs1 (ll u) {
	ll len = 0;
	ll sz = v[u].size ();
	for (int i = 0; i < sz; ++ i) {
		ll y = v[u][i];
		if (vis[y]) {
			continue;
		}
		rem[0] = 0;
		dis[y] = w[u][i];
		get_dis (y, u);
		for (int j = rem[0]; j > 0; -- j) {
			for (int k = 1; k <= m; ++ k) {
				if (q[k] >= rem[j]) {
					test[k] |= judge[q[k] - rem[j]];
				}
			}
		}
		for (int j = rem[0]; j > 0; -- j) {
			t[++ len] = rem[j];
			judge [rem[j]] = 1; 
		}
	}
	for (int i = 1; i <= len; ++ i) {
		judge [t[i]] = 0;
	}
}
void dfs2 (ll u) {
	judge[0] = vis[u] = 1;
	dfs1 (u);
	ll sz = v[u].size ();
	for (int i = 0; i < sz; ++ i) {
		ll y = v[u][i];
		if (vis[y]) {
			continue;
		}
		sum = siz[y];
		maxn[rt] = 1e8;
		rt = 0;
		get_rt (y, u);
		dfs2 (rt);
	}
}
int main () {
	cin >> n >> m;
	for (int i = 1; i < n; ++ i) {
		ll x, y, z;
		cin >> x >> y >> z;
		v[x].push_back (y);
		v[y].push_back (x);
		w[x].push_back (z);
		w[y].push_back (z);
	}
	for (int i = 1; i <= m; ++ i) {
		cin >> q[i];
	}
	maxn[0] = sum = n;
	get_rt (1, 0);
	dfs2 (rt);
	for (int i = 1; i <= m; ++ i) {
		cout << (test[i] ? "AYE\n" : "NAY\n");
	}
	return 0;
}