Tree POJ-1741（树分治）

题意：
给一棵无根树，求任意两点距离小于等于k的点对数量

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX = 10010;
const int INF = 0x3f3f3f3f;
int head[MAX], to[MAX << 1],len[MAX << 1], next[MAX << 1];
int sizee[MAX], deep[MAX], vis[MAX], son[MAX], dis[MAX];
//sizee[x] 表示x的儿子中size最大的是多少
int N, M, root, cnt, tot, ans, all;
//all是当前子树的大小
void add(int x, int y, int z){
    to[++cnt] = y, len[cnt] = z, next[cnt] = head[x], head[x] = cnt;
}void getroot(int x, int fson) {
    son[x] = 0;sizee[x] = 1;for(int i = head[x]; i; i = next[i]) {
    if(to[i] != fson && !vis[to[i]]) {
    getroot(to[i], x);sizee[x] += sizee[to[i]];//将子树to[i]的size加到x上son[x] = max(son[x], sizee[to[i]]);}}son[x] = max(son[x], all - sizee[x]);//除了字数外达到那部分if(son[root] > son[x])//更新rootroot = x;
}
void getdeep(int x, int fson) {
    dis[++tot] = deep[x];for(int i = head[x]; i; i = next[i]) {
    if(to[i] != fson && !vis[to[i]]) {
    deep[to[i]] = deep[x] + len[i];getdeep(to[i], x);}}
}int calc(int x) {
    tot = 0;getdeep(x, 0);sort(dis, dis + tot + 1);;int i = 1, j = tot, sum = 0;while(i < j) {
    if(dis[i] + dis[j] <= M) {
    sum += (j - i);i++;}else j--;}return sum;
}void dfs(int x) {
    deep[x] = 0;vis[x] = 1;ans += calc(x);//cal计算包含根的答案for(int i = head[x]; i; i = next[i]) {
    if(!vis[to[i]]) {
    deep[to[i]] = len[i];//减去字数合并的不合法答案ans -= calc(to[i]);//递归统计字数合并答案all = sizee[to[i]];root = 0;getroot(to[i], 0);dfs(root);}}
}
int main() {
    while(scanf("%d%d", &N, &M) != EOF && N, M) {
    memset(head, 0, sizeof(head));memset(vis, 0, sizeof(vis));cnt = 0; ans = 0;for(int i = 1; i < N; i++) {
    int x, y, z;scanf("%d%d%d", &x, &y, &z);add(x, y, z);add(y, x, z);}son[0] = INF;all = N;root = 0;getroot(1, 0);dfs(root);printf("%d\n", ans);}return 0;
}