洛谷 P2597 分析（别看）

科技起源‍‍‍‍‍‍‍‍‍‍‍‍

2026-08-19 18:49:08

发布于：天津

0阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个具体值

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

背景：
有 $n$ 个点和 $n-1$ 条边
一条 $a\rightarrow b$ 的边代表 $b$ 需要吃 $a$
允许：
定义一个点的灭绝值为“当前点灭绝后有多少点会随之灭绝”

1.3 题目数据范围与猜测

$1 \le n \le 65534 \longrightarrow O(n~log~n)$

1.4 一句话概括题意

有 $n$ 个点， $n-1$ 条边
求每个点灭绝值

2 题目破题推导（正向思维转逆向思维）

因为 $u（非生产者）$ 这个点会灭绝，当且仅当 $u$ 的食物全部灭绝
但是无法直接找到使得 $u$ 所有食物灭绝的点，那么考虑将图转为树，即可找到 $u$ 的所有食物在哪个食物灭绝后会灭绝，随之而来的即为 $u$ 灭绝

3 模型匹配

对正图进行拓扑排序，得到拓扑排序序列
然后是建立灭绝树，首先如果反图没有出边说明它是生产者，则将其与超级源点建立联系，接着遍历拓扑序列中的每一项，如果没有出边就跳过（已经判断过了），其他就是把自己的所有食物的最近公共祖先（这里树并不是提前建好的，而是随着遍历到每一项再单独建立，因为拓扑排序的存在，可以确保当前这一项的所有食物的LCA已经被计算完成）拿出，然后连一条灭绝边（最近公共祖先->当前节点），说明最近公共祖先如果没了，自己也就灭绝了，然后在这里更新f和dep数组
接着是计算灾难值，本质上就是灭绝树底下所有点的数量（就是有多少个点会因为我的灭绝而灭绝，我去发明天才的人真是个灭绝树），然后注意不能直接是size还得-1，因为要排除自己（不可以一开始的时候size=0，否则无法正确进行累加）

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

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

int n;
const int N = 66666, M = 20;
vector<int> g[N];
int in[N];
vector<int> rg[N];
vector<int> tree[N];
vector<int> topo_sort;
void topo(){
    queue<int> q;
    for (int i = 1;i <= n;i++){
        if (in[i] == 0){
            q.push(i);
        }
    }
    while(!q.empty()){
        int f = q.front();
        q.pop();
        topo_sort.push_back(f);
        for (int v : g[f]){
            if (--in[v] == 0){
                q.push(v);
            }
        }
    }
}
int f[N][M];
int dep[N];
int lca(int u, int v){
    if (dep[u] < dep[v]){
        swap(u, v);
    }
    for (int i = 19;i >= 0;i--){
        if (dep[f[u][i]] >= dep[v]){
            u = f[u][i];
        }
    }
    if (u == v){
        return u;
    }
    for (int i = 19;i >= 0;i--){
        if (f[u][i] != f[v][i]){
            u = f[u][i];
            v = f[v][i];
        }
    }
    return f[u][0];
}
void build(){
    for (int now : topo_sort){
        if (rg[now].size() == 0){
            tree[0].push_back(now);
            f[now][0] = 0;
            dep[now] = dep[0] + 1;
            for (int j = 1; j < M; j++) {
                f[now][j] = f[f[now][j - 1]][j - 1];
            }
            continue;
        }
        int lcaa = rg[now][0];
        for (int nowv : rg[now]){
            lcaa = lca(lcaa, nowv);
        }
        tree[lcaa].push_back(now);
        f[now][0] = lcaa;
        dep[now] = dep[lcaa] + 1;
        for (int j = 1; j < M; j++) {
            f[now][j] = f[f[now][j - 1]][j - 1];
        }
    }
}
int ans[N];
int dfs(int u){
    int size = 1;
    for (int v : tree[u]){
        size += dfs(v);
    }
    ans[u] = size - 1;
    return size;
}

int main(){

    cin >> n;
    for (int i = 1;i <= n;i++){
        int x;
        while(cin >> x && x != 0){
            g[x].push_back(i);
            in[i]++;
            rg[i].push_back(x);
        }
    }
    topo();
    build();
    dfs(0);
    for (int i = 1;i <= n;i++){
        cout << ans[i] << endl;
    }
    
    return 0;
}