树分治

点分治

点分治适合处理大规模的树上路径信息问题。

Luogu P4178 Tree

给定一棵有 \(n\) 个点的带权树，给出 \(k\)，询问树上距离小于等于 \(k\) 的点对数量。

分治地考虑每一个子树，求出重心，对答案有贡献的是三种点对，依次解决。

1. 重心 - 子树上的点

   直接累加贡献即可。

2. 子树上的点 - 另一个子树上的点

   记录下每个点到重心的距离 \(p\)，如果两个点的距离不超过 \(k\)，则说明这两个点到重心的距离和不超过 \(k\)，即 \(p_u+p_v \le k\)。

   可以把当前子树的 \(p\) 数组排序，双指针求得点对数量，容易发现这对总复杂度产生了一个 \(\log n\) 的贡献。

3. 子树上的点 - 同一个子树上的点

   这种点对应该在子树中分治地求解，但有些点对可能会产生 \(u\)-重心-\(v\) 形（\(u,v\) 同子树）。

   这时只需删除重复统计的贡献，对子树用一遍双指针删去即可。

yxc 的代码细节值得反复欣赏（进行了些许魔改）。

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

const int maxn = 1e5 + 5;
int n, m;
int q[maxn], p[maxn];
bool del[maxn];
int head[maxn], tot;
struct node{ int v, w, nxt; } e[maxn];
void add(int u, int v, int w){ e[++tot].v = v, e[tot].w = w, e[tot].nxt = head[u],head[u] = tot; }

int get_size(int u, int fa)
{
	if (del[u]) return 0;
	int ret = 1;
	for (int i = head[u]; i; i = e[i].nxt)
	{
		int v = e[i].v;
		if (v != fa) ret += get_size(v, u);
	}
	return ret;
}

int get_wc(int u, int fa, int siz, int &wc) // 求重心，返回子树大小
{
	if (del[u]) return 0;
	int sum = 1, ms = 0; // 最大子树
	for (int i = head[u]; i; i = e[i].nxt)
	{
		int v = e[i].v;
		if (v == fa) continue;
		int c = get_wc(v, u, siz, wc);
		ms = max(ms, c);
		sum += c;
	}
	ms = max(ms, siz - sum);
	if (ms <= siz / 2) wc = u;
	return sum;
}

void get_dist(int u, int fa, int dist, int &qt) // 求子树上各点到重心的距离
{
	if (del[u]) return;
	q[qt++] = dist;
	for (int i = head[u]; i; i = e[i].nxt)
	{
		int v = e[i].v, w = e[i].w;
		if (v != fa) get_dist(v, u, dist + w, qt);
	}
}

int get(int a[], int len)
{
	sort(a, a + len);
	int res = 0;
	for (int l = -1, r = len - 1; r >= 0; r--)
	{
		while (l + 1 < r && a[l + 1] + a[r] <= m)
			l++;
		l = min(l, r - 1);
		res += l + 1;
	}
	return res;
}

int solve(int u)
{
	if (del[u]) return 0;
	int ans = 0;
	get_wc(u, -1, get_size(u, -1), u);
	del[u] = 1;
	int pt = 0;
	for (int i = head[u]; i; i = e[i].nxt)
	{
		int v = e[i].v, qt = 0;
		get_dist(v, -1, e[i].w, qt); // 求出子树 j 上各点到重心的距离
		ans -= get(q, qt);			 // *减去子树 j 的内部不合法贡献
		for (int k = 0; k < qt; k++)
		{
			if (q[k] <= m) ans++;	// 加上重心到当前点路径
			p[pt++] = q[k];			// 记录已经搜过的
		}
	}
	ans += get(p, pt); //*隔着重心的点的贡献
	for (int i = head[u]; i; i = e[i].nxt) //*两个端点
	{
		int v = e[i].v;
		ans += solve(v);
	}
	return ans;
}

signed main()
{
	cin >> n;
	for (int i = 1; i <= n - 1; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w), add(v, u, w);
	}
	cin >> m;
	cout << solve(1) << endl;
	return 0;
}