思路大纲

本题有前置题目: [[problem: luogu, P2014]]

本题目的核心:

证明: 是一个内向基环树
循环依赖的处理: 缩点
证明缩点后加虚拟节点一定是一棵数,每个点的只有一个出边,缩点后一定有n-1条边,且连通,所以是树
转成 luogu P2014 这个题目的问题

题目解析

这是一份基于你提供的大纲，为你量身定制的 P2515 [HAOI2010] 软件安装 详细解析。

P2515 [HAOI2010] 软件安装题目解析

前置题目：[[problem: luogu, P2014]] ([CTSC1997] 选课)

本题本质上是 P2014 选课 的 图论加强版。它在标准的树形背包模型之上，增加了一层循环依赖的处理。

1. 图论建模：证明图的结构

首先，我们需要理清图的形态。

建边规则：

设软件 $i$ 依赖于 $d_i$ 。为了方便分析依赖链，我们建立一条从依赖者指向被依赖者的有向边： $i \to d_i$ 。

如果 $d_i = 0$ ，则视为 $i \to 0$ （指向虚拟源点）。

性质证明（内向基环树森林）：

出度限制：根据题意，一个软件最多依赖一个软件。这意味着图中每一个节点 $i$ 的出度 $out\_degree(i) = 1$ （指向它的依赖对象，或者 0）。
必然存在环：在一个有向图中，如果每个点的出度都为 1，且点数有限，沿着边走下去，必然会遇到重复的点，从而形成环。
基环树形态：这种“每个点只有一条出边”的图，被称为内向函数图 (Functional Graph)。它的每个连通分量形状像一个“水母”或“ $\rho$ ”字形：一个环，周围挂着若干棵指向环的树。

结论：原图是由若干个内向基环树（包含环）或内向树（最终指向 0）组成的森林。

2. 循环依赖的处理：SCC 缩点

问题：标准的树形 DP 只能在 DAG（有向无环图）或树上进行。如果依赖关系中存在环（例如 $A \to B \to C \to A$ ），意味着 $A, B, C$ 互为前置条件。

逻辑推导：

如果想安装环上的任意一个软件，必须先安装它的前置；
一圈推导下来，结论是：要么整个环上的软件都安装，要么都不安装。

解决方案：

使用 Tarjan 算法求强连通分量 (SCC)。

将同一个 SCC 中的所有点缩成一个“超点”。
新重量 $W'_{scc} = \sum w_i$ （环内所有点重量之和）。
新价值 $V'_{scc} = \sum v_i$ （环内所有点价值之和）。

坑点 : 处理孤立环

这是本题最容易出错的边界情况。

在缩点后的图中，可能存在入度为 0 的 SCC。这包含两种情况：

原图中依赖 $0$ 的点（显式依赖根）。
孤立的环：原图中 $A \leftrightarrow B$ ，且 $A, B$ 不依赖其他人。缩点后，这个 SCC 在新图中没有父亲。

处理方案：

统计所有 SCC 的入度。如果某个 SCC 的入度为 $0$ ，说明它没有前置依赖（或者它是一个独立的闭环系统，只要付出代价就能启动），我们必须强制将其连在虚拟根节点 0 下面。

经过上述处理，图变成了一个以 $0$ 为根节点，所有其他 SCC 都有且仅有一个入边的结构——即一棵树。

3. 证明：缩点 + 虚拟节点 = 一棵树

这是本题最关键的转化步骤。为什么缩点后，加上节点 0，就一定能跑树形 DP？

证明过程：

缩点后的出度：

在原图中，每个点 $u$ 只有 1 条出边 $u \to d_u$ 。

缩点后，对于新的超点 $U$ ：
- 如果原边 $u \to d_u$ 是环内边，则该边消失（包含在 $U$ 内部）。
- 如果原边指向环外，那么这个超点 $U$ 依然只有 1 条指向其他 SCC 的出边。
- 结论：缩点后的图（DAG），每个节点依然满足出度 $\le 1$ 。
虚拟根节点的连接：

我们将原图中所有 $d_i=0$ 的边，视为指向虚拟节点 0。

此时，缩点后的图中，所有原本“没有依赖”或者“依赖链终点”的节点，现在都指向了 0 号点。
边的反转（依赖关系 $\to$ 也就是父子关系）：

为了进行树形 DP，我们需要将图看作“父 $\to$ 子”的结构（选了父才能选子）。

我们将上述分析中的边方向反转：由 $d_i \to i$ 。
- 根节点：0 号点。它没有入边（反转前没有出边），它是唯一的源头。
- 入度唯一性：在反转前，每个点出度为 1；反转后，除了根节点 0，每个点（或 SCC 超点）的入度恰好为 1。

最终结论：

一个有 $N'$ 个节点（含虚拟根）的连通图，且除了根节点外，所有节点的入度均为 1，这正是树的定义。

4. 转化为 P2014 选课 (树形背包 DP)

经过上述处理，问题已经完全转化：

节点：缩点后的 SCC 超点。
结构：一棵以 0 为根的树。
限制：背包容量 $M$ 。
规则：想选子节点（子树），必须选父节点。

这与 P2014 [CTSC1997] 选课 完全一致，只是物品的“体积”从 1 变成了 $W_{scc}$ 。

状态转移方程：

设 $dp[u][j]$ 为以 $u$ 为根的子树，花费 $j$ 容量能获得的最大价值。

dp[u][j] = \max_{0 \le k \le j - W_u} (dp[u][j-k] + dp[v][k]) + V_u

初始化：对于节点 $u$ ，必须先花费 $W_u$ 的代价选自己，才能考虑子树。
- $dp[u][j] = V_u \quad (\text{当 } j \ge W_u)$
- $dp[u][j] = 0 \quad (\text{当 } j < W_u)$
分组背包过程：
- 外层枚举子节点 $v$ 。
- 中层倒序枚举容量 $j$ （从 $M$ 到 $W_u$ ）。
- 内层枚举分给子树 $v$ 的容量 $k$ 。

总结流程

建图： $i \to d_i$ 。
Tarjan：找环，缩点，统计每个 SCC 的总重量和总价值。
重构图：
- 建立新图，若原边 $i \to d_i$ 跨越了两个 SCC ( $U \to V$ )，则在新图中建立反向边 $V \to U$ （父指向子）。
- 若 $d_i = 0$ ，建立 $0 \to SCC_i$ 。
树形 DP：从 0 号点开始 DFS，跑一遍分组背包即可。
答案： $dp[0][M]$ 。

代码

cpp

/**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * date: 2025-12-30 19:41:41
 */
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
typedef  unsigned long long ull;

const int maxn = 1e2+5;
const int maxe = 5e2+5;
const int mod = 1e9+7;

int n,m;
int w[maxn];
int _V[maxn];
int scc_w[maxn]; // 缩点后的值
int scc_v[maxn]; // 缩点后的值
int father[maxn]; // father[i]
int dp[maxn][505];

int in_degree[maxn]; // 用于统计 SCC 的入度


bool connect[maxn][maxn]; // 用于scc去重边


//oisnip_begin code/graph/linklist.cpp 内容开始

// const int maxn = 1e6+5;
// const int maxe = 1e6+5;

struct linkList {
    typedef struct {int u,v,w,next;} edge;
    edge e[maxe];
    int h[maxn],edge_cnt=0;
    linkList(){
        reset();
    }

    void reset() {
        edge_cnt=0;
        memset(h,-1,sizeof(h));
    }

    //遍历点u 周围点
    template<typename U>
    void for_each(int u,U func){
        for(int i = h[u] ; i !=-1;i = e[i].next)
            func(e[i].u,e[i].v,e[i].w); //u v w
    }

    void add(int u,int v,int w=0){
        e[edge_cnt] = {u,v,w,h[u]};
        h[u] = edge_cnt++;
    }
    void add2(int u,int v,int w=0){
        add(u,v,w);
        add(v,u,w);
    }
    //下标访问
    edge& operator[](int i){ return e[i]; }

    // 参考 语法糖
    // https://en.cppreference.com/w/cpp/language/range-for.html
#ifdef __cpp_range_based_for
    // C++ 模板 和 策略模式（Policy） 来消除重复代码。
    // 我们可以定义一个通用的迭代器模板，通过传入不同的“提取器（Getter）”来决定 operator* 返回什么。
    // === 1. 定义数据提取策略 (核心区别) ===
    
    // 策略A: 获取整条边 (对应原本的 Iterator)
    struct UseEdge {
        using ReturnType = edge&; // 定义返回类型
        static ReturnType get(linkList* p, int i) { return p->e[i]; }
    };

    // 策略B: 只获取邻接点v (对应原本的 AdjIterator)
    struct UseAdj {
        using ReturnType = int;   // 定义返回类型
        static ReturnType get(linkList* p, int i) { return p->e[i].v; }
    };

    // === 2. 通用迭代器模板 (复用逻辑) ===
    template<typename Getter>
    struct BaseIterator {
        int i;          // 边的编号
        linkList* p;    // linkList指针
        
        BaseIterator(linkList* p, int i) : p(p), i(i) {}

        // 通用的遍历逻辑
        BaseIterator& operator++() { i = p->e[i].next; return *this; }
        bool operator!=(const BaseIterator& oth) { return i != oth.i; }
        
        // 差异化逻辑：委托给 Getter 处理
        typename Getter::ReturnType operator*() { return Getter::get(p, i); }
    };

    // 定义具体的迭代器别名
    using Iterator    = BaseIterator<UseEdge>;
    using AdjIterator = BaseIterator<UseAdj>;

    // === 3. 通用范围类模板 ===
    template<typename IterT>
    struct BaseRange {
        int start;
        linkList* p;
        BaseRange(linkList* p, int start) : p(p), start(start) {}
        IterT begin() { return IterT(p, p->h[start]); }
        IterT end()   { return IterT(p, -1); }
    };

    // === 4. 接口语法糖 ===
    
    // usage: for(auto& e : list(u))
    BaseRange<Iterator> operator()(int u) { return BaseRange<Iterator>(this, u); }

    // usage: for(int v : list.adj(u))
    BaseRange<AdjIterator> adj(int u) { return BaseRange<AdjIterator>(this, u); }
    
#endif
} e;

//oisnip_end code/graph/linklist.cpp 内容结束

linkList e2;

//oisnip_beginscc.cpp
struct TarjanScc {
    int n, timer;
    std::stack<int> st;
    bool in_stack[maxn];
    int dfn[maxn], low[maxn], scc_id[maxn];
    int scc_cnt; // SCC 的总数

    void set(int _n) {
        n = _n;
        timer = scc_cnt = 0;
        memset(dfn, 0, sizeof(dfn));
        memset(in_stack, 0, sizeof(in_stack));
    }

    // 有向图,不要加father参数
    void dfs(int u) {
        dfn[u] = low[u] = ++timer;
        st.push(u);
        in_stack[u] = true;

        for (int i = e.h[u]; ~i ; i = e[i].next) {
            int v = e[i].v;
            if (!dfn[v]) { // 如果 v 没被访问过
                dfs(v);
                
                // 根据子节点的 low 值更新当前节点的 low 值
                low[u] = std::min(low[u], low[v]);
            } else if (in_stack[v]) { //返祖边, 如果 v 在栈中，说明构成了环
                low[u] = std::min(low[u], dfn[v]);
            }
        }

        // 如果 dfn == low，说明找到了一个 SCC 的起始点
        if (low[u] == dfn[u]) {
            scc_cnt++;
            while (1) {
                int v = st.top(); st.pop();
                in_stack[v] = 0;
                scc_id[v] = scc_cnt; // 标记所属 SCC 编号
                scc_w[scc_cnt] += w[v];
                scc_v[scc_cnt] += _V[v];
                if (v == u) break; // 直到找到起始点
            }
        }
    }

    void solve() {
        for (int i = 1; i <= n; i++) {
            if (!dfn[i]) dfs(i);
        }
    }
};
//oisnip_end
TarjanScc tj;


void init(){
    std::cin >> n >> m;
    for(int i = 1;i <= n ;++i ) // i: 1->n
        std::cin >> w[i];
    for(int i = 1;i <= n ;++i ) // i: 1->n
        std::cin >> _V[i];
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        std::cin >> father[i];
        if( father[i] != 0)
            e.add(father[i],i); //反向建图
        // 父亲指向孩子
        // 如果孩子选, 那么父亲必须选
    }

}

// 树形背包 DP
void dfs_dp(int u) {
    // 初始化当前节点 u 的状态
    // 必须选 u 才能选它的子树，所以基础花费是 scc_w[u]，基础收益是 scc_v[u]
    // 其实就是一个子树都不选的状态,就是边界

    for(int j = scc_w[u] ;j <= m; j++)
        dp[u][j] = scc_v[u];

    for(int v : e2.adj(u)) {

        // 后序遍历
        dfs_dp(v);
        // 初始化当前节点 u 的状态
        // 必须选 u 才能选它的子树，所以基础花费是 scc_w[u]，基础收益是 scc_v[u]

        for(int j = m ;j >= scc_w[u];j--){

            // 枚举分给子树 v 的容量 k
            // k 不能超过 j - scc_w[u] (必须留出 u 自己的空间)
            // 就是 枚举组合的每个物品 : k: 0 1 2 ... 
            for(int k = 0 ;k <= j -scc_w[u] ; k ++)
            {
                dp[u][j] = std::max(dp[u][j] , dp[u][j - k] + dp[v][k]);
            }
        }

    }

}

signed main () {
    ios::sync_with_stdio(false); cin.tie(0);

    init();

    // 2. Tarjan 缩点
    tj.set(n);
    tj.solve();

    // 3. 重建图 (建立 SCC 之间的树边)
    // 虚拟根节点 0，连接所有原本依赖 0 的点或者入度为 0 的 SCC
    // 我们可以直接根据原图的 father[i] 来判断连边
    // 如果原图 u->v，且 u,v 不在同一个 SCC，则连边 scc[u]->scc[v]
    
    // 记录入度以便处理森林的情况（或者简单地按照题意 father[i]=0 的连向 0）
    // 题目中 father[i] 是确定的依赖。
    // 如果 father[i] == 0，说明 i 依赖 0 (虚拟根)。
    // 如果 father[i] != 0，说明 i 依赖 father[i]。
    
    // 逻辑修正：
    // 我们需要把所有没有前驱的 SCC 连到 0 号节点上。
    // 因为 father[i] 给了明确的父子关系，我们可以这样建新图：
    // 遍历所有点 i：
    //   令 u = scc_id[father[i]] (如果 father[i]==0，则 u=0)
    //   令 v = scc_id[i]
    //   如果 u != v，则在新图中添加边 u -> v
    
    // 注意：0 号点本身不需要缩点，它是一个独立的虚拟点，scc_id[0] = 0
    // 0 号点重量为 0，价值为 0 


    //遍历每一条边
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        int u = father[i]; // i 的父亲,表示i 依赖 father[i]
        int v = i;

        int u_scc = (u == 0) ? 0 : tj.scc_id[u];
        int v_scc = tj.scc_id[v];
        if( u_scc != v_scc && connect[u_scc][v_scc] == 0) 
        {
            connect[u_scc][v_scc] = 1;
            e2.add(u_scc,v_scc);
            in_degree[v_scc]++; // 统计入度
        }
    }

    // 坑点!!!! : 孤立的循环依赖环
    // 遍历所有 SCC，如果某个 SCC 在新图中入度为 0，说明它是一个孤立的团
    // 我们需要把它挂在虚拟根节点 0 下面，否则 DFS 进不去
    for(int i = 1; i <= tj.scc_cnt; i++) {
        if(in_degree[i] == 0) {
            // 这里不需要判重，因为如果 connect[0][i] 已经存在
            // 说明它本来就依赖 0，in_degree[i] 就不可能是 0 (如果是依赖0, 上面的循环会增加入度)
            // 所以这里直接连边即可
            e2.add(0, i);
        }
    }

    // 4. DP 求解
    // 0 号点也是一个合法的“物品”（重量0，价值0），从它开始 DFS
    // 这样能自动处理所有的联通分量
    dfs_dp(0);

    std::cout << dp[0][m] << "\n";

    
    return 0;
}

[HAOI2010] 软件安装

目录