点分治

树上分治

分为边分治和点分治，其中只有点分治可以保证 $\log n$ 的复杂度。

分！

1. 找重心
2. 找其他被分开树的重心
3. continue

治！

1. 额...归并
2. 无了

例题1

给定一棵树，树上路径大于 $k$ 的路径总数有多少。

树

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

const int N = 10010, M = N * 2;

int n, m;
int head[N], ver[M], weight[M], next_[M], tot;
bool st[N];
int p[N], q[N];

void add(int x, int y, int z)
{
    ver[tot] = y, weight[tot] = z, next_[tot] = head[x], head[x]  = tot++;
    return ;
}

int get_size(int u, int fa) // 求子树大小
{
    if (st[u]) return 0;
    int res = 1;
    for (int i = head[u]; ~i; i = next_[i])
    {
        if (ver[i] != fa) res += get_size(ver[i], u);
    }
    return res;
}

int get_wc(int u, int fa, int idx, int& wc) // 求一个点，是的他的所有子树的大小不大于 n / 2
{
    if (st[u]) return 0;
    int sum = 1, ms = 0;
    for (int i = head[u]; ~i; i = next_[i])
    {
        int j = ver[i];
        if (j == fa) continue;
        int t = get_wc(j, u, idx, wc);
        ms = max(ms, t);
        sum += t;
	}
    ms = max(ms, idx - sum);
    if (ms <= idx / 2) wc = u;
    return sum;
}

void get_dist(int u, int fa, int dist, int& qt) // 子树中点与点之间的距离 
{
    if (st[u]) return ;
    q[qt++] = dist;
    for (int i = head[u]; ~i; i = next_[i])
    {
        if (ver[i] != fa) get_dist(ver[i], u, dist + weight[i], qt);
    }
}

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

int calc(int u)
{
    if (st[u]) return 0;
    int res = 0;
    get_wc(u, -1, get_size(u, -1), u);
    st[u] = true;  //删除重心 
    int pt = 0;
    for (int i = head[u]; ~i; i = next_[i])
    {
        int j = ver[i], qt = 0;
        get_dist(j, -1, weight[i], qt);
        res -= get(q, qt);
        for (int k = 0; k < qt; k++)
        {
            if (q[k] <= m) res ++;
            p[pt++] = q[k];
        }
    }
    res += get(p, pt);
    for (int i = head[u]; ~i; i = next_[i])
    	res += calc(ver[i]);
    return res;
}

int main()
{
	while(scanf("%d%d", &n, &m), n || m)
	{
		memset(st, 0, sizeof st);
		memset(head, -1, sizeof head);
		tot = 0;
		for (int i = 0; i < n - 1; i++)
		{
			int a, b, c;
			scanf("%d%d%d", &a, &b, &c);
			add(a, b, c), add(b, a, c);
		}
		printf("%d\n", calc(0));
	}
	
	return 0;
}