思路

这道题我们直接进行点分治即可。我们需要实现一下的几个操作：

• FIND-ROOT()：找出重心
• GET-META()：更新最小边数答案
• UPDATE(u, sz)：更新边数数组
• CLEAR()：清除边数数组
• DIVIDE()：点分治

我们一段一段来讲。

代码段

void predfs(int u, int fa)
{
    siz[u] = 1, son[u] = 0;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to, w = edges[i].weight;
        if (to == fa || vis[to])
            continue;
        predfs(to, u);
        siz[u] += siz[to], son[u] = max(siz[to], son[u]);
    }
    son[u] = max(son[u], capacity - siz[u]);
    if (son[u] < son[root])
        root = u;
}

这一段是找重心的代码，很简单我就不解释了。

void getMeta(int u, int fa, int cnt, int dist)
{
    if (dist > k)
        return;
    ans = min(ans, sides[k - dist] + cnt);
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to;
        if (to == fa || vis[to])
            continue;
        getMeta(to, u, cnt + 1, dist + edges[i].weight);
    }
}

这段比较重要。点分治出来之后就进行子树上的答案统计，答案的计算为\(ans=min\{sides[k – dist] + cnt\}\)，其中 sides 数组代表长度为 dist 的最小段数。统计的时候不用担心边重复的问题，因为我们之后 update 操作之后才会让 sides 数组生效。

void update(int u, int fa, int cnt, int dist)
{
    if (dist > k)
        return;
    sides[dist] = min(sides[dist], cnt);
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to;
        if (to == fa || vis[to])
            continue;
        update(to, u, cnt + 1, dist + edges[i].weight);
    }
}

用 DFS 进行更新。

void clear(int u, int fa, int dis)
{
    if (dis >= k)
        return;
    sides[dis] = 1e9;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to;
        if (vis[to] || fa == to)
            continue;
        clear(to, u, dis + edges[i].weight);
    }
}

设置为极大值来覆盖子树恢复答案。

void divide(int u, int sz)
{
    vis[u] = true, sides[0] = 0;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to;
        if (vis[to])
            continue;
        getMeta(to, u, 1, edges[i].weight);
        update(to, u, 1, edges[i].weight);
    }
    clear(u, 0, 0);
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to;
        if (vis[to])
            continue;
        son[0] = capacity = (siz[to] > siz[u]) ? (sz - siz[u]) : (siz[to]);
        root = 0;
        predfs(to, 0);
        divide(root, capacity);
    }
}

点分治是在重心上运行的。在重心上更新子树的信息，然后进行换根保证正确性。

总代码

// P4149.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 200200;
struct edge
{
    int to, nxt, weight;
} edges[MAX_N << 1];
int head[MAX_N], n, k, current, tmpx, tmpy, tmpz, siz[MAX_N], capacity;
int ans = 1e9, sides[1002000], son[MAX_N], root;
bool vis[MAX_N];
inline int read()
{
    int re = 0, flag = 1;
    char ch = getchar();
    while (ch > '9' || ch < '0')
    {
        if (ch == '-')
            flag = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        re = (re << 1) + (re << 3) + ch - '0', ch = getchar();
    return re * flag;
}
void addpath(int src, int dst, int weight)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    edges[current].weight = weight, head[src] = current++;
}
void predfs(int u, int fa)
{
    siz[u] = 1, son[u] = 0;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to, w = edges[i].weight;
        if (to == fa || vis[to])
            continue;
        predfs(to, u);
        siz[u] += siz[to], son[u] = max(siz[to], son[u]);
    }
    son[u] = max(son[u], capacity - siz[u]);
    if (son[u] < son[root])
        root = u;
}
void getMeta(int u, int fa, int cnt, int dist)
{
    if (dist > k)
        return;
    ans = min(ans, sides[k - dist] + cnt);
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to;
        if (to == fa || vis[to])
            continue;
        getMeta(to, u, cnt + 1, dist + edges[i].weight);
    }
}
void update(int u, int fa, int cnt, int dist)
{
    if (dist > k)
        return;
    sides[dist] = min(sides[dist], cnt);
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to;
        if (to == fa || vis[to])
            continue;
        update(to, u, cnt + 1, dist + edges[i].weight);
    }
}
void clear(int u, int fa, int dis)
{
    if (dis >= k)
        return;
    sides[dis] = 1e9;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to;
        if (vis[to] || fa == to)
            continue;
        clear(to, u, dis + edges[i].weight);
    }
}
void divide(int u, int sz)
{
    vis[u] = true, sides[0] = 0;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to;
        if (vis[to])
            continue;
        getMeta(to, u, 1, edges[i].weight);
        update(to, u, 1, edges[i].weight);
    }
    clear(u, 0, 0);
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to;
        if (vis[to])
            continue;
        son[0] = capacity = (siz[to] > siz[u]) ? (sz - siz[u]) : (siz[to]);
        root = 0;
        predfs(to, 0);
        divide(root, capacity);
    }
}
int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n - 1; i++)
    {
        scanf("%d%d%d", &tmpx, &tmpy, &tmpz);
        addpath(tmpx + 1, tmpy + 1, tmpz), addpath(tmpy + 1, tmpx + 1, tmpz);
    }
    capacity = n;
    son[0] = n, root = 0;
    for (int i = 0; i <= k; i++)
        sides[i] = 1e9;
    predfs(1, 0);
    divide(root, n);
    if (ans != 1e9)
        printf("%d", ans);
    else
        printf("-1");
    return 0;
}