树

本题求的是一棵树上长度不超过 $K$ 的路径的数量。

对于这类问题，可以使用点分治算法，点分治就是在一棵树上，对具有某些限定条件的路径静态的进行统计的算法。

本题是一颗无根树，假设指定节点 $p$ 为根，对 $p$ 而言，树上的路径可以分为两类：
1. 经过根节点 $p$
2. 包含于 $p$ 的某一棵树中(不经过根节点)

根据分治的思想，对于第 $2$ 类路径，显然可以把 $p$ 的每棵子树作为子问题，递归进行处理。

对于第 $1$ 类路径，可以从根节点 $p$ 分成 $x \sim p$ 和 $p \sim y$ 两端，可以从 $p$ 出发对整棵树进行 $dfs$，求出数组 $d[]$，其中 $d[x]$ 表示从点 $x$ 到根节点 $p$ 的距离，同时还可以求出数组 $b[]$，其中$b[x]$ 表示点 $x$ 属于根节点 $p$ 的哪一棵子树，令 $b[p] = p$。

此时满足题目要求的第 $1$ 类路径就是满足以下两个条件的点对 $(x, y)$ 的个数。
1. $b[x] \neq b[y]$
2. $d[x] + d[y] \leq K$

定义 $Calc(p)$ 表示在以 $p$ 为根的树中统计上述点对的个数(第 $1$ 类路径的条数)。 $Calc(p)$ 有两种常见的实现方式。针对不同的题目，两者各有优劣。

方法一：树上直接统计

设 $p$ 的子树为 $s_1, s_2, …, s_m$。

对于 $s_i$ 中的每个节点 $x$，把子树 $s_1, s_2, …, s_{i-1}$ 中满足 $d[x] + d[y] \leq K$ 的节点 $y$ 的个数累加到答案中即可。

具体来说，建立一个树状数组，依次处理每棵子树 $s_i$。
1. 对 $s_i$ 中的每个节点 $x$，查询前缀和 $sum(K - d[x])$，即为所求的 $y$ 的个数。
2. 对 $s_i$ 中的每个节点 $x$，执行 $add(d[x], 1)$，表示与 $p$ 距离为 $d[x]$ 的节点增加了 $1$ 个。

按子树一颗颗进行处理保证了 $b[x] \neq b[y]$，查询前缀和保证了 $d[x] + d[y] \leq K$，需要注意的是，树状数组的范围与路径长度有关，这个范围远比 $N$ 要大，而本题中不好离散化，一种方法是用平衡树代替树状数组，保证 $O(Nlog_2N)$ 的复杂度，但代码难写，因此方法二更加适合本题。

方法二：指针扫描数组

把树中每个点放进一个数组 $a[]$，并把数组 $a[]$ 按照节点的 $d$ 值排序。

使用两个指针 $L, R$ 分别从前、后开始扫描 $a[]$ 数组。

在指针 $L$ 从左向右扫描的过程中，恰好使得 $d[a[L]] + d[a[R]] \leq K$ 的指针 $R$ 的范围是从右向左单调递减的。

另外，用数组 $cnt[s]$ 维护在 $L+1$ 到 $R$ 之间满足 $b[a[i]] = s$ 的位置 $i$ 的个数。

于是，当路径的一端 $x$ 等于 $a[L]$ 时，满足题目要求的路径另一端 $y$ 的个数就是 $R-L-cnt[b[a[L]]]$
(由于 $d[a[L]] + d[a[R]] \leq K$，因此 $R-L$ 指所有和 $d[a[L]]$ 相加不超过 $K$ 的数的个数，再减去和 $a[L]$同一个子树的节点，剩下的节点数就是符合条件的 $y$ 的个数)

总而言之，整个点分治算法的过程就是：
1. 任选一个根节点 $p$。
2. 从 $p$ 出发进行一次 $dfs$，求出 $d[]$ 数组和 $b[]$ 数组。
3. 执行 $Calc(p)$
4. 删除根节点 $p$，对 $p$ 的每棵子树(看作无根树)递归执行 $1 \sim 4$ 步。

在点分治的过程中，每一层的所有递归过程合计对每个节点处理 $1$ 次，因此若递归最深达到第 $T$ 层，则整个算法的时间复杂度就是 $O(TNlog_2N)$。

如果问题中的树是一条链，最坏情况下每次都以链的一段为根，那么点分治将需要递归 $N$ 层，时间复杂度退化到 $O(N^2log_2N)$ 为了避免这种情况，可以每次选择树的重心作为根节点 $p$，此时 $p$ 的每棵子树的大小都不会超过整棵树的大小的一半，点分治最多只会递归 $O(log_2n)$ 层，整个算法的时间复杂度为 $O(Nlog^2_2N)$。

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

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

int n, k;
int h[N], e[M], w[M], ne[M], idx; //邻接表
//a[] 按照d值将所有节点从小到大排序
//d[i] 表示第i个节点到根节点的距离
//b[i] 表示第i个节点属于根节点的哪一棵子树
//cnt[i] 表示[L + 1, R]中属于根节点的第i棵子树的节点个数
//s[i] 表示以第i个节点为根节点的子树中的节点个数
int d[N], b[N], cnt[N], s[N], a[N], acnt;
int root; //表示根节点(每次将树的重心作为根节点)
int res; //路径总条数
int ans; //记录删除树的重心后剩余连通块中节点个数的最大值
//st[] 记录每个点是否被删除，true 表示已被删除，false 表示未被删除
bool st[N];

void add(int a, int b, int c) //添加边
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

bool cmp(int a, int b) //比较函数：所有节点按照d值从小到大排序
{
    return d[a] < d[b];
}

void dfs_find(int S, int u, int father) //dfs找重心
{
    s[u] = 1; //当前以u为根节点子树中只发现了u自己

    int maxv = 0; //记录删除u节点后，剩余连通块中节点个数的最大值
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(st[j] || j == father) continue; //如果走到父节点(不能往回走)，或已经被删除，直接跳过

        dfs_find(S, j, u); //搜索子节点
        maxv = max(maxv, s[j]); //用子节点所在的连通块更新节点个数的最大值
        s[u] += s[j]; //更新以u节点为根节点子树的节点个数
    }

    maxv = max(maxv, S - s[u]); //用u节点上面部分的连通块更新节点个数的最大值
    if(maxv < ans) //如果去掉u节点后剩余连通块的节点个数最大值更小
    {
        ans = maxv; //更新节点个数最大值
        root = u; //更新树的重心
    }
}

void dfs(int u, int father)
{
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(st[j] || j == father) continue; //如果走到父节点(不能往回走)，或已经被删除，直接跳过

        b[j] = b[u]; //每个子节点属于父节点所在的子树
        a[++acnt] = j; //将子节点加入a[]数组
        cnt[b[j]]++; //父节点所在的子树中的节点个数+1

        d[j] = d[u] + w[i]; //更新子节点到根节点的距离
        dfs(j, u); //继续搜索子节点
    }
}

void work(int S, int u, int father) //S 表示当前树中节点个数，u表示当前节点
{
    ans = S; //节点数最多之后S个
    dfs_find(S, u, father); //找出当前树的重心作为根节点

    //重置数组
    memset(d, 0, sizeof d);
    memset(cnt, 0, sizeof cnt);

    acnt = 0; //清空a[]数组
    b[root] = root; //root属于自己这颗子树
    a[++acnt] = root; //将root加入a[]数组
    st[root] = true; //将root从原树中删去

    cnt[root]++; //root属于自己这颗子树，a[]数组中属于以root为根节点的子树的节点个数+1
    for(int i = h[root]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(st[j] || j == father) continue; //如果走到父节点(不能往回走)，或已经被删除，直接跳过

        b[j] = j; //j节点是root的子节点，因此j属于root的以j为根节点的子树
        a[++acnt] = j; //将j节点加入a[]数组
        cnt[j]++; //以j为根节点的子树的节点个数+1

        d[j] = w[i]; //j节点到root的距离就是它们之间的边权
        dfs(j, root); //搜索j节点的所有子节点，并将它们加入a[]数组
    }

    sort(a + 1, a + 1 + acnt, cmp); //将所有节点按照d值从小到大排序

    int l = 1, r = acnt; //l, r指针
    while(l < r) //双指针
    {
        cnt[b[a[l]]]--; //cnt[] 维护的是[l + 1, r]之间所有子树的节点个数，需要将l指针指向的节点去掉
        while(d[a[l]] + d[a[r]] > k) //找到最大的r，使得d[l] + d[r] <= k
        {
            cnt[b[a[r]]]--; //将r指针指向的节点去掉
            r--; //r指针左移
        }

        res += r - l - cnt[b[a[l]]]; //累加所有符合的点对数量

        l++; //l指针右移
    }

    for(int i = h[root]; i != -1; i = ne[i]) //枚举当前根节点的所有子节点
    {
        int j = e[i];
        if(st[j]) continue; //如果当前子节点已经被删除，直接跳过

        work(s[j], j, root); //否则递归搜索子节点中符合要求的点对
    }
}

int main()
{
    while(scanf("%d%d", &n, &k), n || k)
    {
        memset(h, -1, sizeof h); //初始化邻接表
        idx = 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); //无向边
        }

        memset(st, 0, sizeof st); //最开始每个节点都还存在
        res = 0; //重置答案
        work(n, 1, -1); //点分治

        printf("%d\n", res);
    }
    return 0;
}