「学习笔记」略谈点分治

typedef pair<int, int> pii;

const int N = 4e4 + 10;

int n, k, rt, ans, sum;
int siz[N], maxp[N], dis[N], ok[N];
bool vis[N];
vector<pii> son[N];

void get_root(int u, int fat) {
	siz[u] = 1;
	maxp[u] = 0;
	for (pii it : son[u]) {
		int v = it.first;
		if (v == fat || vis[v])	continue;
		get_root(v, u);
		siz[u] += siz[v];
		maxp[u] = max(maxp[u], siz[v]);
	}
	maxp[u] = max(maxp[u], sum - siz[u]);
	if (maxp[u] < maxp[rt])	rt = u;
}

int calc(int u, int val) {
	ok[0] = 0;
	dis[u] = val;
	dfs(u, 0);
	sort(ok + 1, ok + ok[0] + 1);
	int cnt = 0, l = 1, r = ok[0];
	while (l < r) {
		if (ok[l] + ok[r] <= k) {
			cnt += (r - l ++);
		}
		else {
			r --;
		}
	}
	return cnt;
}

void work(int u) {
	ans += calc(u, 0);
	vis[u] = 1;
	for (pii it : son[u]) {
		int v = it.first, w = it.second;
		if (vis[v])	continue;
		ans -= calc(v, w);
		maxp[rt = 0] = sum = siz[v];
		get_root(v, 0);
		work(rt);
	}
}

void dfs(int u, int fat) {
	ok[++ ok[0]] = dis[u];
	siz[u] = 1;
	for (pii it : son[u]) {
		int v = it.first, w = it.second;
		if (v == fat || vis[v])	continue;
		dis[v] = dis[u] + w;
		dfs(v, u);
		siz[u] += siz[v];
	}
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int N = 4e4 + 10;

int n, k, rt, ans, sum;
int siz[N], maxp[N], dis[N], ok[N];
bool vis[N];
vector<pii> son[N];

inline ll read() {
	ll x = 0;
	int fg = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		fg |= (ch == '-');
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 3) + (x << 1) + (ch ^ 48);
		ch = getchar();
	}
	return fg ? ~x + 1 : x;
}

void get_root(int u, int fat) {
	siz[u] = 1;
	maxp[u] = 0;
	for (pii it : son[u]) {
		int v = it.first;
		if (v == fat || vis[v])	continue;
		get_root(v, u);
		siz[u] += siz[v];
		maxp[u] = max(maxp[u], siz[v]);
	}
	maxp[u] = max(maxp[u], sum - siz[u]);
	if (maxp[u] < maxp[rt])	rt = u;
}

void dfs(int u, int fat) {
	ok[++ ok[0]] = dis[u];
	siz[u] = 1;
	for (pii it : son[u]) {
		int v = it.first, w = it.second;
		if (v == fat || vis[v])	continue;
		dis[v] = dis[u] + w;
		dfs(v, u);
		siz[u] += siz[v];
	}
}

int calc(int u, int val) {
	ok[0] = 0;
	dis[u] = val;
	dfs(u, 0);
	sort(ok + 1, ok + ok[0] + 1);
	int cnt = 0, l = 1, r = ok[0];
	while (l < r) {
		if (ok[l] + ok[r] <= k) {
			cnt += (r - l ++);
		}
		else {
			r --;
		}
	}
	return cnt;
}

void work(int u) {
	ans += calc(u, 0);
	vis[u] = 1;
	for (pii it : son[u]) {
		int v = it.first, w = it.second;
		if (vis[v])	continue;
		ans -= calc(v, w);
		maxp[rt = 0] = sum = siz[v];
		get_root(v, 0);
		work(rt);
	}
}

int main() {
	n = read();
	for (int i = 1, u, v, w; i < n; ++ i) {
		u = read(), v = read(), w = read();
		son[u].push_back({v, w});
		son[v].push_back({u, w});
	}
	k = read();
	maxp[rt = 0] = sum = n;
	get_root(1, 0);
	work(rt);
	printf("%d\n", ans);
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, ll> pil;

const int N = 1e4 + 5;

int n, m, sum, rt;
int q[N], siz[N], maxs[N], can[N], dis[N];
int tp[N];
bool ok[N], vis[N];
vector<pil> son[N];

bool cmp(int x, int y) {
	return dis[x] < dis[y];
}

void get_root(int u, int fat, int tot) {
	siz[u] = 1;
	maxs[u] = 0;
	for (auto [v, w] : son[u]) {
		if (v == fat || vis[v])	continue;
		get_root(v, u, tot);
		siz[u] += siz[v];
		maxs[u] = max(siz[v], maxs[u]);
	}
	maxs[u] = max(maxs[u], tot - siz[u]);
	if (!rt || maxs[u] < maxs[rt]) {
		rt = u;
	}
}

void dfs(int u, int fat, int d, int from) {
	can[++ can[0]] = u;
	dis[u] = d;
	tp[u] = from;
	for (auto [v, w] : son[u]) {
		if (v == fat || vis[v])	continue;
		dfs(v, u, d + w, from);
	}
}

void calc(int u) {
	can[0] = 0;
	can[++ can[0]] = u;
	dis[u] = 0;
	tp[u] = u;
	for (auto [v, w] : son[u]) {
		if (vis[v])	continue;
		dfs(v, u, w, v);
	}
	sort(can + 1, can + can[0] + 1, cmp);
	for (int i = 1; i <= m; ++ i) {
		int l = 1, r = can[0];
		if (ok[i])	continue;
		while (l < r) {
			if (dis[can[l]] + dis[can[r]] > q[i]) {
				r --;
			}
			else if (dis[can[l]] + dis[can[r]] < q[i]) {
				++ l;
			}
			else if (tp[can[l]] == tp[can[r]]) {
				if (dis[can[r]] == dis[can[r - 1]]) {
					-- r;
				}
				else ++ l;
			}
			else {
				ok[i] = true;
				break;
			}
		}
	}
}

void work(int u) {
	vis[u] = true;
	calc(u);
	for (auto [v, w] : son[u]) {
		if (vis[v])	continue;
		rt = 0;
		get_root(v, 0, siz[v]);
		work(rt);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1, x, y, z; i < n; ++ i) {
		cin >> x >> y >> z;
		son[x].push_back({y, z});
		son[y].push_back({x, z});
	}
	for (int i = 1; i <= m; ++ i) {
		cin >> q[i];
		if (!q[i])	ok[i] = 1;
	}
	maxs[0] = n;
	get_root(1, 0, n);
	work(rt);
	for (int i = 1; i <= m; ++ i) {
		if (ok[i]) {
			cout << "AYE" << '\n';
		}
		else {
			cout << "NAY" << '\n';
		}
	}
	return 0;
}