洛谷 P2018 分析（别看）

科技起源的小号1

2026-08-28 15:46:12

发布于：天津

2阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个最小值和最小值对应的可行方案

1.2 题目背景、允许、禁止与限制

背景：
国家中有 $N$ 个人
国家中的人成如下关系： $1$ 个国王（没有上级）， $N-1$ 个人，如果 $A$ 是 $B$ 的上级， $B$ 是 $C$ 的上级，则称 $A$ 也是 $C$ 的上级
允许：
现在有条消息，你作为国王要传播这条消息
使用 $1$ 单位时间将这条消息传播给 $1$ 个人（之前被传播过消息的人也可以同时传播给其直接上级或直接下级） $\rightarrow$ 发现这两种情况貌似都是“沿着边传播”！所以其实本质上不用考虑“传播给直接上级”，因为可以被“传播给直接下级”平替
求最短需要多少单位时间可以把这条消息传播给所有人，以及从哪些点（也就是以哪些点为根节点）开始传播可以达到这个最短时间

1.3 题目数据范围与猜测

$n \le 1000 \longrightarrow O(n^2)$

1.4 一句话概括题意

有一棵树，求这棵树上沿边传播消息的最短时间

2 题目破题推导

2.1 第一步：画图模拟+贪心思路

画一颗这样的树

发现只有这样的传播顺序，才能使整体耗费时间最短

那么我们有个基本贪心思路：传播顺序是按照子树内部传播时间从大到小

2.2 第二步：证明贪心思路

传播时间越长的子树越应该先被通知，因为早点开始可以让它的"长耗时"和"等待时间"重叠，从而减少总体时间。

类比现实生活：如果有多个任务要分配，最耗时的任务应该最先开始，这样总完成时间最短——这就是流水线调度中的经典贪心策略（Johnson法则的简化版）

这里不写数学证明了，自己思考

3 模型匹配

树形结构、最短时间、多次求答案--> 树形dp
设 $dp[i]$ 为以 $i$ 为根的整棵子树都被传播到的最小时间
刚刚我们已经知道了传播的顺序
那对于这个点，整体传播完时间究竟是多久呢？答案是：

$\underset{v是u的孩子}{min}\left(dp[v] + i(v是第几个被u传播的) - 1 \right)$

4 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;

int n;
const int N = 1111;
vector<int> g[N];
bool cmp(int x, int y){
    return x > y;
}
int dp[N];
void dfs(int u, int fa){
    int temp[N] = {0}, cnt = 0;
    for (int v : g[u]){
        if (v == fa) continue;
        dfs(v, u);
        temp[++cnt] = dp[v];
    }
    sort(temp + 1, temp + 1 + cnt, cmp);
    for (int i = 1;i <= cnt;i++){
        dp[u] = max(dp[u], temp[i] + i - 1);
    }
    dp[u]++;// 用 1 单位的时间把一个消息告诉某一个人
}
int ans[N];

int main(){

    cin >> n;
    for (int i = 2;i <= n;i++){
        int j;
        cin >> j;
        g[i].push_back(j);
        g[j].push_back(i);
    }
    int mn = INT_MAX;
    for (int i = 1;i <= n;i++){
        memset(dp, 0, sizeof(dp));
        dfs(i, -1);
        ans[i] = dp[i];
        mn = min(mn, dp[i]);
    }
    cout << mn << endl;
    for (int i = 1;i <= n;i++){
        if (ans[i] == mn){
            cout << i << " ";
        }
    }
    
    return 0;
}