AcWing 264. 权值 题解

题目分析

本题给定一棵有(N)个节点的树，每条边有权值，要求找出一条简单路径，使得路径上各边权值和等于(K)，并且路径包含的边数量最少。如果不存在这样的路径，则输出(-1)。

解题思路

本题采用树的重心分治算法，结合动态规划的思想来求解。通过不断找到树的重心，将树分解，在每个子树中计算满足权值和为(K)的最少边数路径，并记录全局最优解。
1. 构建邻接表：使用add函数构建树的邻接表，方便后续对树进行遍历和操作。
2. 计算子树大小：get_size函数用于计算以某个节点为根的子树大小，为寻找树的重心提供基础。
3. 寻找树的重心：get_wc函数找到树或子树的重心，以保证每次分治时子树的大小尽量平衡，优化时间复杂度。
4. 计算路径信息：get_dist函数从某个节点出发，计算到其所有子节点的路径权值和以及边的数量，并记录下来。
5. 分治计算与动态规划：calc函数以树的重心为分界点，递归地在子树中进行计算。通过动态规划的方式，利用已经计算出的路径信息，更新满足权值和为(K)的最少边数路径，并去除重复计算的部分。

代码逐段分析

1. 头文件和全局变量定义

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

#define x first
#define y second

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;
int f[S], ans = INF;
PII p[N], q[N];
bool st[N];

• 引入必要的头文件，包括输入输出、字符串操作和算法相关的头文件。
• 使用宏定义x和y分别表示pair类型的第一个和第二个元素。
• 定义PII为pair<int, int>的别名。
• 定义常量(N)表示树的节点数，(M)表示边数的两倍（因为是无向图），(S)用于动态规划数组的大小，INF表示一个极大值。
• 变量(n)表示节点数，(m)表示目标权值和(K)。
• h[N]是邻接表的头指针数组，e[M]存储边的另一端节点，w[M]存储边的权值，ne[M]指向下一条边的下标，idx用于记录边的编号。
• f[S]是动态规划数组，用于存储权值和为某个值时的最少边数；ans用于记录满足条件的最少边数，初始化为极大值INF。
• p[N]和q[N]用于存储路径的权值和以及边的数量信息。

• st[N]用于标记节点是否已被处理（在分治过程中删除）。

• 添加边函数

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

• 该函数用于向邻接表中添加一条边，从节点a到节点b，权值为c。

• 计算子树大小函数

int get_size(int u, int fa)
{
    if (st[u]) return 0;
    int res = 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        res += get_size(j, u);
    }
    return res;
}

• 该函数递归计算以节点u为根的子树大小。如果节点u已被处理（st[u]为true），则返回(0)。否则，初始子树大小为(1)（包含节点u自身），然后遍历节点u的所有子节点（排除父节点fa），递归计算子树大小并累加。

• 寻找树的重心函数

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; 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;
}

• 该函数用于寻找以节点u为根的子树的重心。如果节点u已被处理，则返回(0)。
• 初始化子树大小sum为(1)，最大子树大小ms为(0)。遍历节点u的所有子节点（排除父节点fa），递归计算子树大小t，更新ms为已遍历子树中的最大子树大小，并累加子树大小sum。

• 计算以节点u为根的子树中，除当前子树外的其他部分的大小（tot - sum），并更新ms。如果ms不超过子树总大小tot的一半，则节点u为重心，将其赋值给wc。最后返回子树大小sum。

• 计算路径信息函数

void get_dist(int u, int fa, int dist, int cnt, int& qt)
{
    if (st[u] || dist > m) return;
    q[qt ++ ] = {dist, cnt};
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        get_dist(j, u, dist + w[i], cnt + 1, qt);
    }
}

• 该函数从节点u出发，计算到其所有子节点的路径权值和dist以及边的数量cnt，并将结果以pair的形式存储在数组q中。如果节点u已被处理或者路径权值和超过目标值m，则返回。

• 将当前路径的权值和与边数存入数组q，然后遍历节点u的所有子节点（排除父节点fa），递归计算子节点的路径信息。

• 分治计算与动态规划函数

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; i = ne[i])
    {
        int j = e[i], qt = 0;
        get_dist(j, u, w[i], 1, qt);
        for (int k = 0; k < qt; k ++ )
        {
            auto& t = q[k];
            if (t.x == m) ans = min(ans, t.y);
            ans = min(ans, f[m - t.x] + t.y);
            p[pt ++ ] = t;
        }
        for (int k = 0; k < qt; k ++ )
        {
            auto& t = q[k];
            f[t.x] = min(f[t.x], t.y);
        }
    }
    for (int i = 0; i < pt; i ++ )
        f[p[i].x] = INF;

    for (int i = h[u]; ~i; i = ne[i]) calc(e[i]);
}

• 该函数以节点u为起点进行分治计算。如果节点u已被处理，则返回。
• 首先找到节点u所在子树的重心，并标记重心已被处理（从树中删除）。
• 遍历重心的所有子节点，计算每个子节点到其所有子节点的路径信息：
  • 若路径权值和等于目标值m，则更新ans为当前路径的最少边数与ans中的较小值。
  • 利用动态规划思想，通过f[m - t.x] + t.y更新ans，其中f[m - t.x]是之前计算得到的权值和为m - t.x的最少边数。
  • 将路径信息存储在数组p中。
  • 更新动态规划数组f，记录权值和为p[i].x时的最少边数。
• 计算完当前重心子树的路径信息后，将相关权值和对应的最少边数重置为极大值INF，以避免重复计算。

• 递归地对重心的所有子节点进行分治计算。

• 主函数

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);
    calc(0);

    if (ans == INF) ans = -1;
    printf("%d\n", ans);

    return 0;
}

• 主函数读入树的节点数n和目标权值和m。
• 初始化邻接表头指针数组h，并根据输入构建树的邻接表。
• 初始化动态规划数组f为极大值。
• 从节点(0)开始调用calc函数进行分治计算。
• 如果最终ans仍为极大值INF，说明不存在满足条件的路径，将ans设为(-1)，然后输出结果。

时间复杂度分析

• 每次寻找重心和计算子树大小的时间复杂度为(O(n))，由于树的重心分治每次能将树分成两部分，递归次数为(O(\log n))，所以这部分总时间复杂度为(O(n \log n))。
• 在每个子树中计算路径信息和更新动态规划数组的时间复杂度，由于路径数量最多为子树节点数，所以这部分时间复杂度也为(O(n \log n))。
• 因此，本题的时间复杂度为(O(n \log n))。

空间复杂度分析

主要空间消耗在于邻接表相关数组、标记数组、存储路径信息的数组以及动态规划数组等，空间复杂度为(O(n + K))，其中(K)是目标权值和 。