权值问题

解题思路

本题要求所有权值和等于 $k$ 的路径中，边的数量的最小值。

本题是一个查询树上信息的问题，可以考虑用点分治来求。首先找到重心，然后整棵树被重心分成若干个子部分。此时所有路径被分成三大类。第一类是路径的端点在同一棵子树中。第二类是路径的端点在不同的子树中。第三类是路径的某一个端点是重心。

对于第一类路径，我们可以直接递归到子树中去处理。对于第三类路径，我们直接从重心往下 $dfs$ 一遍求出所有点到重心的距离，如果某个点到重心的距离恰好等于 $k$，就更新一下边数最小值。

对于第二类，我们需要枚举所有端点在不同子树中的路径。可以发现这一类路径都一定经过重心，因此这种路径都可以分成一个子树中的某个点到重心的一段加上另一个子树中的某个点到重心的一段。这里可以一棵子树一棵子树的枚举，处理第一棵子树时，此时还不存在这一类的路径，因此不需要求。处理第二棵子树时，如果某个点到重心的距离时 $x$，那么我们就是要在前面枚举过的所有子树中找出一个到重心距离为 $k-x$ 的点，由于我们要求的是边数最小的路径，因此如果前面的子树中如果有多个点到重心的距离是 $k-x$，那么我们其实只需要记录到重心的边数最小的一个点。由于 $k$ 的范围不大，所以我们可以开一个数组 $f_y$，表示前面枚举的所有子树中到重心距离是 $y$ 的所有路径中边数的最小值。这样对于当前枚举的某个点，我们就能快速求出他和前面所有点构成的长度为 $k$ 的路径的边数最小值。枚举完当前子树之后，我们再将当前子树中的所有点更新到 $f$ 数组中，给下一个枚举的子树继续用。

然后为了保证每棵子树内的处理都是线性的时间复杂度，在重置 $f$ 数组时需要只重置用过的位置，这里可以用一个数组记录一下用过的所有位置，便于重置。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

typedef pair<int, int> PII;

const int N = 200010, M = N * 2, S = 1000010, INF = 0x3f3f3f3f;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
bool st[N];
//p[i] 存储所有子树中的每个点到重心的距离和边数
//q[i] 存储当前子树中的每个点到重心的距离和边数
PII p[N], q[N];
int f[S]; //f[i] 表示前面所有子树中到重心距离为 i 的路径的边数最小值
int res = INF; //记录答案

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

int get_size(int u, int fa) //求 u 所在子树的大小
{
    if(st[u]) return 0;
    int res = 1;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j == fa) continue;
        res += get_size(j, u);
    }
    return res;
}

int get_wc(int u, int fa, int tot, int &wc) //求重心，并返回子树大小
{
    if(st[u]) return 0;
    int sum = 1, ms = 0;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j == fa) continue;
        int t = get_wc(j, u, tot, wc);
        ms = max(ms, t);
        sum += t;
    }
    ms = max(ms, tot - sum);
    if(ms <= tot / 2) wc = u;
    return sum;
}

//求一下当前子树中的所有点到重心的距离和边数
//dist 表示 u 到重心的距离
//cnt 表示 u 到重心的边数
void get_dist(int u, int fa, int dist, int cnt, int &qt)
{
    if(st[u] || dist > m) return; //被删的点、到重心的距离 > m 的点不需要考虑
    q[qt++] = {dist, cnt};
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j == fa) continue;
        get_dist(j, u, dist + w[i], cnt + 1, qt);
    }
}

void calc(int u) //点分治
{
    if(st[u]) return;
    get_wc(u, -1, get_size(u, -1), u); //求重心
    st[u] = true; //将重心删去

    //归并子树之间的信息
    int pt = 0;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        int qt = 0;
        get_dist(j, -1, w[i], 1, qt); //求一下当前子树中的所有点到重心的距离和边数
        for(int k = 0; k < qt; k++)
        {
            auto &t = q[k];
            if(t.first == m) res = min(res, t.second); //更新第三类路径
            res = min(res, f[m - t.first] + t.second); //更新第二类路径
            p[pt++] = t; //将当前节点存入整棵子树的数组中
        }
        for(int k = 0; k < qt; k++) //用当前子树的信息更新 f
        {
            auto &t = q[k];
            f[t.first] = min(f[t.first], t.second);
        }
    }
    for(int i = 0; i < pt; i++)  f[p[i].first] = INF; //重置 f

    for(int i = h[u]; i != -1; i = ne[i]) calc(e[i]); //递归处理每棵子树
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h); //初始化邻接表

    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(f, 0x3f, sizeof f); //初始化 f
    calc(0); //点分治

    if(res == INF) res = -1; //如果 res = INF，说明无解
    printf("%d\n", res);

    return 0;
}