526互联

点分治模板

发布时间 2023-03-28 15:07:25作者: Galetx

洛谷P3806

#include <bits/stdc++.h>
using namespace std;

int read() {
	int s = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9')
		f = (ch == '-' ? -1 : 1), ch = getchar();
	while (ch >= '0' && ch <= '9')
		s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
	return s * f;
}

int n, m, k;
int head[10005], to[20005], nxt[20005], val[20005], tot = 0;
int ht, Maxp, d[10005], sz[10005];
bool f[10005];

void add(int u, int v, int w) {
	to[++tot] = v, nxt[tot] = head[u], val[tot] = w, head[u] = tot;
}

bool v[10000005];

void H(int p, int fa, int SZ) {
	int maxp = 0;
	sz[p] = 1;
	for (int i = head[p]; i; i = nxt[i])
		if (to[i] != fa && !f[to[i]])
			H(to[i], p, SZ), sz[p] += sz[to[i]], maxp = max(maxp, sz[to[i]]);
	maxp = max(maxp, SZ - sz[p]);
	if (maxp < Maxp)
		Maxp = maxp, ht = p;
}

void getd(int p, int fa) {
	for (int i = head[p]; i; i = nxt[i])
		if (to[i] != fa && !f[to[i]])
			d[to[i]] = d[p] + val[i], getd(to[i], p);
}

void mdf(int p, int fa, bool val) {
	if (d[p] > k)
	    return ;
	v[d[p]] = val;
	for (int i = head[p]; i; i = nxt[i])
		if (to[i] != fa && !f[to[i]])
			mdf(to[i], p, val);
}

bool qry(int p, int fa) {
    if (d[p] > k)
        return false;
	if (v[k - d[p]])
		return true;
	for (int i = head[p]; i; i = nxt[i])
		if (to[i] != fa && !f[to[i]] && qry(to[i], p))
			return true;
	return false;
}

bool Solve(int rt) {
	Maxp = 1e9, H(rt, 0, sz[rt]), rt = ht;
	d[rt] = 0, v[0] = true, getd(rt, 0);
	bool ans = false;
	for (int i = head[rt]; i; i = nxt[i]) {
		if (f[to[i]])
			continue;
		ans |= qry(to[i], rt), mdf(to[i], rt, true);
	}
	for (int i = head[rt]; i; i = nxt[i])
		if (!f[to[i]])
			mdf(to[i], rt, false);
	if (ans)
		return ans;
	f[rt] = true;
	for (int i = head[rt]; i; i = nxt[i])
		if (!f[to[i]] && Solve(to[i]))
			return true;
	return false;
}

signed main() {
	n = read(), m = read();
	for (int i = 2; i <= n; i++) {
		int u = read(), v = read(), w = read();
		add(u, v, w), add(v, u, w);
	}
	while (m--) {
		k = read();
		memset(f, 0, sizeof f);
		puts(Solve(1) ? "AYE" : "NAY");
	}
	return 0;
}