题解：旅行商人问题（CCO 2023 Day2 T2）

一、题目核心分析

1. 问题本质

给定一棵包含 $N$ 个城市的树，每个城市有利润 $p_i$（仅能获取一次）。商人从城市 $1$ 出发，需在连续超过 $K$ 天无利润的约束下，访问城市并最大化总利润，同时输出最优路线（做生意的城市顺序）。

2. 关键约束与观察

• 树结构特性：任意两城市间路径唯一，移动需消耗时间（1天/道路）；
• 利润约束：连续 $K+1$ 天无利润会被解雇，即两次获利的时间间隔不能超过 $K$ 天；
• $K$ 的范围极小（$1 \leq K \leq 3$）：可针对 $K=1,2,3$ 设计针对性的动态规划（DP）策略；
• 最大化利润的核心：优先访问高利润城市，且需满足时间约束（路径长度 ≤ 两次获利的时间间隔）。

3. 核心思路

按 $K$ 的取值分类讨论：

• $K=1$：两次获利的时间间隔 ≤1 天 → 路径为“城市1 → 直接相邻城市”（无中间移动时间），本质是求以城市1为起点的最长路径（单链）；
• $K=2$：两次获利的时间间隔 ≤2 天 → 可访问“城市1 → 中转城市 → 目标城市”（中间允许1次移动），需考虑分支路径的组合；
• $K=3$：两次获利的时间间隔 ≤3 天 → 可覆盖更复杂的分支组合，此时所有城市的利润均可获取（因树的直径 ≤ 2×(N-1)，但 $K=3$ 足够支持遍历所有节点而不触发解雇条件），总利润为所有城市利润之和。

二、完整代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define N 200000
using namespace std;

void dfs5(int x);

// 快速读入（适配大数据量）
int read() {
    char c = 0;
    int sum = 0;
    while (c < '0' || c > '9') c = getchar();
    while ('0' <= c && c <= '9') sum = sum * 10 + c - '0', c = getchar();
    return sum;
}

int n, k, a[N + 1], fa[N + 1], tong[N + 1], length;
long long ans, dp[N + 1], dp2[N + 1], dp3[N + 1];
vector<int>E[N + 1];
bool used[N + 1];

// 添加树边（无向）
void add(int x, int y) {
    E[x].push_back(y), E[y].push_back(x);
    return;
}

// K=1 时的DFS：计算以x为根的子树中，从根出发的最大利润路径（单链）
void dfs(int x) {
    used[x] = 1;
    for (int i = 0; i < E[x].size(); ++i)
        if (!used[E[x][i]]) {
            fa[E[x][i]] = x;
            dp[E[x][i]] = dp[x] + a[E[x][i]]; // 路径利润累加
            dfs(E[x][i]);
        }
    return;
}

// K=2 时的DP预处理：计算三个关键DP数组
// dp[x]：以x为根，仅选一个子树的最大利润（单链）
// dp2[x]：以x为根，选一个或两个子树的最大利润（支持K=2的约束）
// dp3[x]：以x为根，选三个子树的最大利润（辅助计算dp2）
void dfs2(int x) {
    int rt = 0, rt2 = 0; // 利润最大的两个子树节点
    long long res = 0, res2 = 0, res3 = 0; // 子树的最大利润（不含自身a[x]）
    used[x] = 1;
    dp[x] = dp2[x] = dp3[x] = a[x]; // 初始利润为自身利润

    // 递归处理子树
    for (int i = 0; i < E[x].size(); ++i)
        if (!used[E[x][i]]) {
            fa[E[x][i]] = x;
            dfs2(E[x][i]);
        }

    // 统计子树的前三大利润（不含自身a[x]）
    for (int i = 0; i < E[x].size(); ++i)
        if (fa[E[x][i]] == x) {
            long long sub = dp[E[x][i]] - a[E[x][i]]; // 子树利润（不含子树根的a）
            if (sub > res) {
                res3 = res2;
                res2 = res;
                rt2 = rt;
                res = sub;
                rt = E[x][i];
            } else if (sub > res2) {
                res3 = res2;
                res2 = sub;
                rt2 = E[x][i];
            } else if (sub > res3) {
                res3 = sub;
            }
        }

    // 更新dp[x]（单链最大利润）和临时最大值rst、rst2
    dp[x] += res;
    long long rst = max(rst, res); // 单个子树的最大利润
    long long rst2 = max(rst2, res + res2); // 两个子树的最大利润和

    // 结合子树的dp2、dp3更新rst和rst2（考虑子树内部的多分支）
    for (int i = 0; i < E[x].size(); ++i)
        if (fa[E[x][i]] == x) {
            long long sub_dp2 = dp2[E[x][i]] - a[E[x][i]];
            long long sub_dp3 = dp3[E[x][i]] - a[E[x][i]];
            // 更新单个分支的最大利润（当前子树的dp2 + 其他最大子树利润）
            if (E[x][i] != rt) rst = max(rst, sub_dp2 + res);
            else rst = max(rst, sub_dp2 + res2);
            // 更新两个分支的最大利润（当前子树的dp2 + 另外两个最大子树利润）
            if (E[x][i] == rt) rst2 = max(rst2, sub_dp2 + res2 + res3);
            else if (E[x][i] == rt2) rst2 = max(rst2, sub_dp2 + res + res3);
            else rst2 = max(rst2, sub_dp2 + res + res2);
            // 更新两个分支的最大利润（当前子树的dp3 + 其他最大子树利润）
            if (E[x][i] != rt) rst2 = max(rst2, sub_dp3 + res);
            else rst2 = max(rst2, sub_dp3 + res2);
        }

    // 更新dp2和dp3
    dp2[x] += rst;
    dp3[x] += rst2;
    // 考虑子树的dp3直接叠加当前节点a[x]的情况
    for (int i = 0; i < E[x].size(); ++i)
        if (fa[E[x][i]] == x)
            dp2[x] = max(dp2[x], dp3[E[x][i]] + a[x]);

    return;
}

// 回溯路径：K=1时的单链路径（type=0：先根后子；type=1：先子后根）
void dfs3(int x, int type) {
    long long dst = a[x];
    if (!type) {
        // 计算当前节点的子树总a值（不含父节点）
        for (int i = 0; i < E[x].size(); ++i)
            if (fa[E[x][i]] == x)
                dst += a[E[x][i]];
        // 找到贡献最大的子树，优先遍历
        for (int i = 0; i < E[x].size(); ++i)
            if (fa[E[x][i]] == x) {
                if (dst + dp[E[x][i]] - a[E[x][i]] == dp[x]) {
                    // 先遍历其他子树（非最大贡献）
                    for (int j = 0; j < E[x].size(); ++j)
                        if (fa[E[x][j]] == x && E[x][j] != E[x][i])
                            tong[++length] = E[x][j];
                    // 递归遍历最大贡献子树
                    dfs3(E[x][i], 1);
                    tong[++length] = x;
                    return;
                }
            }
    } else {
        // 计算当前节点的子树总a值（不含父节点）
        for (int i = 0; i < E[x].size(); ++i)
            if (fa[E[x][i]] == x)
                dst += a[E[x][i]];
        // 找到贡献最大的子树，优先遍历
        for (int i = 0; i < E[x].size(); ++i)
            if (fa[E[x][i]] == x) {
                if (dst + dp[E[x][i]] - a[E[x][i]] == dp[x]) {
                    tong[++length] = x;
                    dfs3(E[x][i], 0);
                    // 后遍历其他子树（非最大贡献）
                    for (int j = 0; j < E[x].size(); ++j)
                        if (fa[E[x][j]] == x && E[x][j] != E[x][i])
                            tong[++length] = E[x][j];
                    return;
                }
            }
    }
    // 无子树贡献，直接添加当前节点
    tong[++length] = x;
    return;
}

// 回溯路径：K=2时的dp2路径（对应最大利润）
void dfs4(int x) {
    int rt = 0, rt2 = 0;
    long long dst = a[x], res = 0, res2 = 0, res3 = 0;
    // 计算当前节点的子树总a值（不含父节点）
    for (int i = 0; i < E[x].size(); ++i)
        if (fa[E[x][i]] == x)
            dst += a[E[x][i]];
    // 统计子树的前三大利润（不含自身a[x]）
    for (int i = 0; i < E[x].size(); ++i)
        if (fa[E[x][i]] == x) {
            long long sub = dp[E[x][i]] - a[E[x][i]];
            if (sub > res) {
                res3 = res2;
                res2 = res;
                rt2 = rt;
                res = sub;
                rt = E[x][i];
            } else if (sub > res2) {
                res3 = res2;
                res2 = sub;
                rt2 = E[x][i];
            } else if (sub > res3) {
                res3 = sub;
            }
        }

    // 情况1：dp2[x]由单个最大子树贡献
    if (dst + res == dp2[x]) {
        tong[++length] = x;
        if (rt) dfs3(rt, 0);
        // 添加其他子树
        for (int i = 0; i < E[x].size(); ++i)
            if (fa[E[x][i]] == x && E[x][i] != rt)
                tong[++length] = E[x][i];
        return;
    }

    // 情况2：dp2[x]由当前子树的dp2 + 其他子树利润贡献
    for (int i = 0; i < E[x].size(); ++i)
        if (fa[E[x][i]] == x) {
            long long sub_dp2 = dp2[E[x][i]] - a[E[x][i]];
            if (E[x][i] != rt) {
                if (dst + sub_dp2 + res == dp2[x]) {
                    tong[++length] = x;
                    if (rt) dfs3(rt, 0);
                    // 添加其他子树
                    for (int j = 0; j < E[x].size(); ++j)
                        if (fa[E[x][j]] == x && E[x][j] != rt && E[x][j] != E[x][i])
                            tong[++length] = E[x][j];
                    dfs4(E[x][i]);
                    return;
                }
            } else {
                if (dst + sub_dp2 + res2 == dp2[x]) {
                    tong[++length] = x;
                    if (rt2) dfs3(rt2, 0);
                    // 添加其他子树
                    for (int j = 0; j < E[x].size(); ++j)
                        if (fa[E[x][j]] == x && E[x][j] != rt2 && E[x][j] != E[x][i])
                            tong[++length] = E[x][j];
                    dfs4(E[x][i]);
                    return;
                }
            }
        }

    // 情况3：dp2[x]由子树的dp3 + 当前节点a[x]贡献
    for (int i = 0; i < E[x].size(); ++i)
        if (fa[E[x][i]] == x && dp3[E[x][i]] + a[x] == dp2[x]) {
            tong[++length] = x;
            dfs5(E[x][i]);
            return;
        }

    // 无其他贡献，直接添加当前节点
    tong[++length] = x;
    return;
}

// 回溯路径：K=2时的dp3路径（对应多分支组合）
void dfs5(int x) {
    int rt = 0, rt2 = 0, rt3 = 0;
    long long dst = a[x], res = 0, res2 = 0, res3 = 0;
    // 计算当前节点的子树总a值（不含父节点）
    for (int i = 0; i < E[x].size(); ++i)
        if (fa[E[x][i]] == x)
            dst += a[E[x][i]];
    // 统计子树的前三大利润（不含自身a[x]）
    for (int i = 0; i < E[x].size(); ++i)
        if (fa[E[x][i]] == x) {
            long long sub = dp[E[x][i]] - a[E[x][i]];
            if (sub > res) {
                res3 = res2;
                res2 = res;
                rt3 = rt2;
                rt2 = rt;
                res = sub;
                rt = E[x][i];
            } else if (sub > res2) {
                res3 = res2;
                rt3 = rt2;
                res2 = sub;
                rt2 = E[x][i];
            } else if (sub > res3) {
                res3 = sub;
                rt3 = E[x][i];
            }
        }

    // 情况1：dp3[x]由两个最大子树贡献
    if (dst + res + res2 == dp3[x]) {
        if (rt) dfs3(rt, 0);
        tong[++length] = x;
        if (rt2) dfs3(rt2, 1);
        // 添加其他子树
        for (int i = 0; i < E[x].size(); ++i)
            if (fa[E[x][i]] == x && E[x][i] != rt && E[x][i] != rt2)
                tong[++length] = E[x][i];
        return;
    }

    // 情况2：dp3[x]由当前子树的dp2 + 另外两个子树利润贡献
    for (int i = 0; i < E[x].size(); ++i)
        if (fa[E[x][i]] == x) {
            long long sub_dp2 = dp2[E[x][i]] - a[E[x][i]];
            if (E[x][i] == rt) {
                if (dst + sub_dp2 + res2 + res3 == dp3[x]) {
                    if (rt2) dfs3(rt2, 1);
                    tong[++length] = x;
                    if (rt3) dfs3(rt3, 0);
                    // 添加其他子树
                    for (int j = 0; j < E[x].size(); ++j)
                        if (fa[E[x][j]] == x && E[x][j] != rt2 && E[x][j] != rt3 && E[x][j] != E[x][i])
                            tong[++length] = E[x][j];
                    dfs4(E[x][i]);
                    return;
                }
            } else if (E[x][i] == rt2) {
                if (dst + sub_dp2 + res + res3 == dp3[x]) {
                    if (rt) dfs3(rt, 1);
                    tong[++length] = x;
                    if (rt3) dfs3(rt3, 0);
                    // 添加其他子树
                    for (int j = 0; j < E[x].size(); ++j)
                        if (fa[E[x][j]] == x && E[x][j] != rt && E[x][j] != rt3 && E[x][j] != E[x][i])
                            tong[++length] = E[x][j];
                    dfs4(E[x][i]);
                    return;
                }
            } else {
                if (dst + sub_dp2 + res + res2 == dp3[x]) {
                    if (rt) dfs3(rt, 1);
                    tong[++length] = x;
                    if (rt2) dfs3(rt2, 0);
                    // 添加其他子树
                    for (int j = 0; j < E[x].size(); ++j)
                        if (fa[E[x][j]] == x && E[x][j] != rt && E[x][j] != rt2 && E[x][j] != E[x][i])
                            tong[++length] = E[x][j];
                    dfs4(E[x][i]);
                    return;
                }
            }

            // 情况3：dp3[x]由当前子树的dp3 + 其他子树利润贡献
            long long sub_dp3 = dp3[E[x][i]] - a[E[x][i]];
            if (E[x][i] != rt) {
                if (dst + sub_dp3 + res == dp3[x]) {
                    // 添加其他子树
                    for (int j = 0; j < E[x].size(); ++j)
                        if (fa[E[x][j]] == x && E[x][j] != rt && E[x][j] != E[x][i])
                            tong[++length] = E[x][j];
                    if (rt) dfs3(rt, 1);
                    tong[++length] = x;
                    dfs5(E[x][i]);
                    return;
                }
            } else {
                if (dst + sub_dp3 + res2 == dp3[x]) {
                    // 添加其他子树
                    for (int j = 0; j < E[x].size(); ++j)
                        if (fa[E[x][j]] == x && E[x][j] != rt2 && E[x][j] != E[x][i])
                            tong[++length] = E[x][j];
                    if (rt2) dfs3(rt2, 1);
                    tong[++length] = x;
                    dfs5(E[x][i]);
                    return;
                }
            }
        }

    // 无其他贡献，直接添加当前节点
    tong[++length] = x;
    return;
}

// K=3时的路径遍历（前序遍历，确保所有节点都被访问）
void dfs6(int x, int type) {
    used[x] = 1;
    if (!type) {
        tong[++length] = x; // 先访问当前节点
        for (int i = 0; i < E[x].size(); ++i)
            if (!used[E[x][i]])
                dfs6(E[x][i], 1);
    } else {
        for (int i = 0; i < E[x].size(); ++i)
            if (!used[E[x][i]])
                dfs6(E[x][i], 0);
        tong[++length] = x; // 后访问当前节点
    }
    return;
}

int main() {
    int x, y;
    n = read(), k = read();

    // 建图
    for (int i = 1; i <= n - 1; ++i) {
        x = read(), y = read();
        add(x, y);
    }

    // 读入每个城市的利润
    for (int i = 1; i <= n; ++i)
        a[i] = read();

    if (k == 1) {
        // K=1：求以1为起点的最长单链路径
        dp[1] = a[1];
        dfs(1);

        // 找到最大利润对应的终点
        ans = 0;
        for (int i = 1; i <= n; ++i)
            if (dp[i] > ans) {
                ans = dp[i];
                x = i;
            }

        // 回溯路径（从终点到起点，再反转）
        length = 0;
        while (x) {
            tong[++length] = x;
            x = fa[x];
        }
        reverse(tong + 1, tong + length + 1);

        // 输出结果
        printf("%lld\n", ans);
        printf("%d\n", length);
        for (int i = 1; i <= length; ++i)
            printf("%d ", tong[i]);
        puts("");
    } else if (k == 2) {
        // K=2：DP预处理 + 路径回溯
        fill(used, used + n + 1, false);
        dfs2(1);
        length = 0;
        dfs4(1);

        // 输出结果
        printf("%lld\n", dp2[1]);
        printf("%d\n", length);
        for (int i = 1; i <= length; ++i)
            printf("%d ", tong[i]);
        puts("");
    } else {
        // K=3：所有城市均可访问，总利润为所有a[i]之和
        ans = 0;
        for (int i = 1; i <= n; ++i)
            ans += a[i];

        // 前序遍历输出路径
        length = 0;
        fill(used, used + n + 1, false);
        dfs6(1, 0);

        // 输出结果
        printf("%lld\n", ans);
        printf("%d\n", length);
        for (int i = 1; i <= length; ++i)
            printf("%d ", tong[i]);
        puts("");
    }

    return 0;
}

三、分情况详细讲解

1. 情况 1：$K=1$

核心逻辑**

$K=1$ 意味着两次获利的时间间隔不能超过 1 天。由于移动需要 1 天，因此商人只能访问与当前获利城市直接相邻的城市（否则会出现连续 2 天无利润）。本质是求以城市 1 为起点的最长路径（单链）（树的直径的一部分）。

实现步骤

1. DFS 计算最大利润路径：dfs 函数递归遍历树，dp[x] 表示从城市 1 到城市 $x$ 的路径利润之和，fa[x] 记录父节点（用于回溯路径）。
2. 找到最大利润终点：遍历所有节点，找到 dp[x] 最大的节点 $x$（路径终点）。
3. 回溯路径：从终点 $x$ 沿 fa 数组回溯到起点 1，再反转路径得到做生意的城市顺序。

样例 1 解析

输入：

4 1
1 2
1 3
2 4
3 1 4 1

• 城市 1 的相邻城市为 2（利润 1）和 3（利润 4）；
• 最长路径为 1→3（利润 3+4=7）；
• 输出路径为 [1,3]，与样例一致。

2. 情况 2：$K=2$

核心逻辑

$K=2$ 允许两次获利的时间间隔不超过 2 天，即商人可以访问“当前城市 → 中转城市 → 目标城市”（中间移动 1 天，无利润，再获利 1 天，总间隔 2 天）。需考虑分支路径的组合，因此设计三个 DP 数组：

• dp[x]：以 $x$ 为根，仅选择一个子树的最大利润（单链）；
• dp2[x]：以 $x$ 为根，选择一个或两个子树的最大利润（支持 $K=2$ 约束）；
• dp3[x]：以 $x$ 为根，选择三个子树的最大利润（辅助计算 dp2）。

实现步骤

1. DP 预处理（dfs2 函数）：
   • 递归处理所有子树，统计每个子树的前三大利润（不含子树根的利润）；
   • 更新 dp[x]（单链最大利润）、dp2[x]（单/双分支最大利润）、dp3[x]（三分支最大利润）。
2. 路径回溯（dfs4、dfs5、dfs3 函数）：
   • 根据 dp2[x] 的来源（单分支、双分支、子树 dp3 贡献），递归回溯路径；
   • 优先遍历高利润子树，确保路径顺序符合获利约束。

3. 情况 3：$K=3$

核心逻辑

$K=3$ 允许两次获利的时间间隔不超过 3 天，此时商人可以遍历树中所有节点而不触发解雇条件（树的任意两节点间路径长度 ≤ $2 \times (N-1)$，但 $K=3$ 足够支持“移动-移动-移动-获利”的间隔）。因此最大利润为所有城市利润之和，路径可通过前序遍历获得。

实现步骤

1. 计算总利润：累加所有城市的利润 $a[i]$；
2. 前序遍历树：dfs6 函数按前序遍历（先访问当前节点，再递归子节点）输出路径，确保所有节点都被包含。

四、关键函数解析

1. 快速读入 read()

适配 $N \leq 2 \times 10^5$ 的大数据量，避免输入超时。

2. DP 预处理 dfs2()

核心是统计子树的前三大利润，结合子树的 DP 结果更新当前节点的 DP 值，确保覆盖所有符合 $K=2$ 约束的分支组合。

3. 路径回溯函数（dfs3-dfs5）

根据 DP 数组的计算逻辑，反向推导最优路径的生成过程，优先选择高利润分支，确保路径顺序满足“连续不超过 $K$ 天无利润”的约束。

4. 前序遍历 dfs6()

用于 $K=3$ 时输出所有节点的路径，保证每个节点都被访问且路径顺序合法。

五、复杂度分析

• 时间复杂度：$O(N)$。所有函数均为线性遍历树，无嵌套循环，适配 $N \leq 2 \times 10^5$ 的数据范围。
• 空间复杂度：$O(N)$。存储树的邻接表、DP 数组、路径数组，均为线性空间。

六、样例解析

样例 2

输入：

5 2
1 2
1 3
2 4
2 5
3 1 4 1 5

• $K=2$，最大利润为所有城市利润之和（3+1+4+1+5=14）；
• 路径为 1→4→5→2→3（对应访问路线 1→2→4→2→5→2→1→3），满足所有获利间隔 ≤2 天；
• 输出结果与样例一致。

总结

本题的核心是利用 $K$ 极小的特性，按 $K$ 的取值分类设计策略：

• $K=1$ 聚焦单链最长路径；
• $K=2$ 通过多维度 DP 覆盖分支组合；
• $K=3$ 直接遍历所有节点。 路径回溯的关键是反向推导 DP 数组的计算逻辑，确保路径顺序符合获利约束。整体算法效率高，适配大数据量，且能正确输出最优路径。