题解

算法分析

本题是一个典型的 树链剖分 + 线段树 应用问题，属于 数据结构 中的 树链剖分 和 区间维护 问题。

问题本质

我们需要维护一棵依赖树（每个软件包依赖一个父软件包），支持两种操作：

1. 安装操作：安装一个软件包需要安装从根节点到该节点的所有软件包
2. 卸载操作：卸载一个软件包需要卸载其整个子树的所有软件包

解题思路

1. 树链剖分：

   • 将树转化为线性序列，便于区间操作
   • 通过两次 DFS 计算每个节点的深度、子树大小、重儿子、所在链的顶端、DFS 序等信息

2. 线段树维护：

   • 使用线段树维护每个节点的安装状态（0 表示未安装，1 表示已安装）
   • 支持区间赋值和区间求和操作

3. 安装操作：

   • 从当前节点向上跳到根节点，统计路径上未安装的节点数
   • 将路径上的所有节点标记为已安装

4. 卸载操作：

   • 直接统计子树中已安装的节点数
   • 将整个子树标记为未安装

算法标签

• 树链剖分
• 线段树
• 树上的路径查询与更新
• DFS 序

关键代码解析

// 树链剖分的两次DFS
void dfs1(int u, int f) {  // 计算子树大小、重儿子
    // ...
}

void dfs2(int u, int tp) {  // 分配DFS序、确定链顶
    // ...
}

// 安装操作：从节点x向上到根节点
int UpdPath(int x) {
    int ans = 0;
    while (x) {
        int tp = G[x].top;
        // 计算当前链上未安装的节点数
        int L = ST.Query(1, 1, n, G[tp].dfn, G[x].dfn);
        int R = G[x].dfn - G[tp].dfn + 1;
        ans += R - L;
        // 将当前链标记为已安装
        ST.Update(1, 1, n, G[tp].dfn, G[x].dfn, 1);
        x = G[tp].fa;
    }
    return ans;
}

// 卸载操作：卸载整个子树
int UpdSub(int x) {
    // 统计子树中已安装的节点数
    int L = ST.Query(1, 1, n, G[x].dfn, G[x].dfn + G[x].sz - 1);
    // 将子树标记为未安装
    ST.Update(1, 1, n, G[x].dfn, G[x].dfn + G[x].sz - 1, 0);
    return L;
}

时间复杂度

• 树链剖分预处理：$O(n)$
• 每次安装操作：$O(\log^2 n)$（树链剖分路径操作）
• 每次卸载操作：$O(\log n)$（线段树区间操作）
• 总体复杂度：$O(n + q \log^2 n)$，能够处理 $n, q \leq 10^5$ 的数据规模

空间复杂度

• $O(n)$，用于存储树结构和线段树

总结

本题通过树链剖分将树上的路径操作转化为区间操作，结合线段树高效维护安装状态，是树链剖分的经典应用。关键在于理解安装操作需要处理从节点到根的路径，而卸载操作需要处理整个子树。