luogu3806 点分治模板

题目链接

每次找重心，然后处理每个子树。

// luogu-judger-enable-o2
#include<bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define LL long long
#define SZ(X) X.size()
#define pii pair<int,int>
#define ALL(X) X.begin(),X.end()

using namespace std;

LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}
LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}
LL powmod(LL a, LL b, LL MOD) {LL ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
const int N = 1e4 + 11;
int n, m;
vector<pii>v[N];
int q[N];
int rt, son[N], sz[N], vis[N];
void root(int now, int pre) { //找重心
	sz[now] = 1;
	son[now] = 0;
	for (auto k : v[now]) {
		if (vis[k.fi] || k.fi == pre)continue;
		root(k.fi, now);
		sz[now] += sz[k.fi];
		son[now] = max(son[now], sz[k.fi]);
	}
	son[now] = max(son[now], n - sz[now]);
	if (!rt || son[rt] > son[now]) {
		rt = now;
	}
	return ;
}
int a[N], dis[10000003];
int md[N], MK, cnt;
void getdis(int now, int pre, int di) {
	if (di > MK)return ;
	md[++cnt] = di;
	for (auto k : v[now]) {
		if (vis[k.fi] || k.fi == pre)continue;
		getdis(k.fi, now, di + k.se);
	}
}
int qa[N], tmp;
void get(int now, int pre) {
	dis[0] = 1;
	for (auto k : v[now]) {
		if (k.fi == pre || vis[k.fi])continue;
		cnt = 0;
		getdis(k.fi, now, k.se);
		for (int i = 1; i <= cnt; ++i) {
			for (int j = 1; j <= m; j++) {
				if (q[j] >= md[i])a[j] |= dis[q[j] - md[i]];
			}
		}
		for (int i = 1; i <= cnt; i++)dis[md[i]] = 1, qa[++tmp] = md[i];
	}
}
void dfs(int now) {
	vis[now] = 1;
	tmp = 0;
	get(now, 0);
	for (int i = 1; i <= tmp; i++)dis[qa[i]] = 0;
	for (auto k : v[now]) {
		if (vis[k.fi])continue;
		rt = 0;
		n = sz[k.fi];
		root(k.fi, 0);
		dfs(rt);
	}
	return ;
}
int main() {
	// freopen("1.in", "r", stdin);
	scanf("%d %d", &n, &m);
	for (int i = 1; i < n; i++) {
		int s, t, w;
		scanf("%d%d%d", &s, &t, &w);
		v[s].pb({t, w});
		v[t].pb({s, w});
	}
	for (int i = 1; i <= m; i++)scanf("%d", &q[i]), MK = max(q[i], MK);
	root(1, 0);
	root(rt, 0);
	dfs(rt);
	for (int i = 1; i <= m; i++)puts(a[i] ? "AYE" : "NAY");
	return 0;
}