12974.大量的工作沟通

markdown
复制
1# 大量的工作沟通 题解
2
3## 题目分析
4
5题目中的管理关系可以抽象为一棵 **有根树**：
6
7- 根节点是 `0` 号员工（老板）。
8- 除老板外，每名员工有一个直接领导，形成树上的父子边。
9- 员工 `x` 能管理员工 `y` **当且仅当 `x` 是 `y` 的祖先（或 `x = y`）**。
10
11现在有若干次合作，每次合作给出参与员工的集合，要求选出一名员工主持合作，该员工必须能管理所有参与者。如果有多名满足条件的员工，选择 **编号最大** 的那一个。
12
13**关键转化**：能管理所有参与者的员工，等价于 **所有参与员工在树上的公共祖先**。显然，所有公共祖先恰好是从根节点到所有参与者最近公共祖先（LCA）**这条路径上的所有节点**。因此，问题转化为：
14
151. 求给定节点集合的最近公共祖先 `lca`。
162. 在 **根节点到 `lca` 的路径上** 找出编号最大的员工。
17
18---
19
20## 解题思路
21
221. **建树**  
23   输入给的是每个员工的直接领导，根据这些信息建立有根树，根为 `0`。  
24   为了方便处理，通常把编号统一转为 `1-based`（`0` 变成 `1`，其他依次加 `1`）。
25
262. **预处理：求路径最大值**  
27   在 `DFS` 遍历树的过程中，可以顺便求出从根节点到当前节点的路径上 **编号的最大值**，记为 `mxId[u]`。  
28   递推公式：`mxId[u] = max(u, mxId[fa[u]])`。
29
303. **预处理：快速求 LCA**  
31   常用方法有 **树上倍增** 或 **树链剖分**。参考代码使用了树链剖分：  
32   - 第一遍 `DFS`：求出每个节点的父节点、深度、子树大小、重儿子，同时完成 `mxId` 的计算。  
33   - 第二遍 `DFS`：求出每个节点所在重链的链顶 `tp`。  
34   - `lca(x, y)` 函数：不断将链顶深度较深的节点跳到链顶的父节点，直到两点在同一重链为止，此时深度较小的即为 LCA。
35
364. **处理询问**  
37   对于每次合作，给出 `m` 个参与员工。将这 `m` 个员工两两求 LCA（或顺序合并），最终得到所有员工的 LCA `p`。  
38   答案即为 `mxId[p]`（最后别忘了将编号转回 `0-based`）。
39
40---
41
42## 算法说明（以参考代码为例）
43
44参考代码采用了树链剖分求 LCA 的做法，具体步骤如下：
45
46### 数据结构定义
47
48```cpp
49const int N = 100005;
50int fa[N], sz[N], dep[N], son[N], tp[N], mxId[N];
51int cnt, fir[N], tar[N], nxt[N];

• fa[x]：x 的父节点。
• dep[x]：x 的深度。
• sz[x]：以 x 为根的子树大小。
• son[x]：x 的重儿子（子树最大的子节点）。
• tp[x]：x 所在重链的链顶节点。
• mxId[x]：根到 x 路径上的最大编号。
• fir, tar, nxt：链式前向星存图。

建图与编号转换

cpp
复制
1int n;
2scanf("%d", &n);
3for (int i = 2; i <= n; i++) {
4    scanf("%d", &fa[i]);
5    link(++fa[i], i);          // 0-based 转 1-based
6}

员工编号从 0 到 N-1，在代码中统一映射为 1 到 N，根节点为 1。

第一遍 DFS：求 sz, son, dep, mxId

cpp
复制
1void dfs(int x, int mxid) {
2    int Mx = 0;
3    sz[x] = 1;
4    mxId[x] = max(x, mxid);       // 更新路径最大编号
5    for (int i = fir[x]; i; i = nxt[i]) {
6        dep[tar[i]] = dep[x] + 1;
7        dfs(tar[i], mxId[x]);     // 将当前路径最大值传给儿子
8        sz[x] += sz[tar[i]];
9        if (Mx < sz[tar[i]]) {    // 更新重儿子
10            Mx = sz[son[x] = tar[i]];
11        }
12    }
13}
14dfs(1, 1);

由于根节点为 1，初始路径最大编号也设为 1。

第二遍 DFS：求链顶 tp

cpp
复制
1void gettp(int x) {
2    tp[x] = x;
3    if (son[fa[x]] == x)         // 如果 x 是父节点的重儿子，则与父节点同链
4        tp[x] = tp[fa[x]];
5    for (int i = fir[x]; i; i = nxt[i])
6        gettp(tar[i]);
7}
8gettp(1);

LCA 查询

cpp
复制
1int lca(int x, int y) {
2    while (tp[x] != tp[y]) {
3        if (dep[tp[x]] > dep[tp[y]])
4            x = fa[tp[x]];
5        else
6            y = fa[tp[y]];
7    }
8    return dep[x] < dep[y] ? x : y;
9}

处理每次询问

cpp
复制
1int q;
2scanf("%d", &q);
3while (q--) {
4    int m, x, y;
5    scanf("%d%d", &m, &x);
6    x++;                           // 转为 1-based
7    for (int i = 2; i <= m; i++) {
8        scanf("%d", &y);
9        x = lca(x, ++y);           // 不断将当前 LCA 与新节点求 LCA
10    }
11    cout << mxId[x] - 1 << endl;   // 转回 0-based 输出
12}

这里使用了 顺序合并法：设当前 LCA 为 cur，依次加入每个新节点并更新 cur = lca(cur, new_node)，最终 cur 就是所有节点的 LCA。正确性基于 LCA 的结合律。

最后，从 mxId[x] 中减去 1 即可得到原始编号（0-based）下的最大编号员工。

---

时间复杂度分析

• 建树与预处理：两遍 DFS 均为 O(N)，求 mxId 也在第一遍 DFS 中顺便完成。
• 单次 LCA 查询：树链剖分每次 LCA 的复杂度为 O(log N)。
• 处理一次询问：共有 m 个员工，需要做 m-1 次 LCA，复杂度为 O(m log N)。
• 总复杂度：所有询问的 m 之和最大约为 Q × max(m) = 100 × 10^4 = 10^6，log N ≈ 17，因此总运算量在百万级别，足以在 1000ms 内轻松通过。

---

注意事项

• 编号转换要小心：题目是 0-based，存图时可采用 1-based，最后输出时切回 0-based。
• 0 号老板是根节点，在 1-based 下为 1，其 mxId 即为 1。
• 由于题目保证 m ≥ 2 且编号合法不重复，无需处理空集合或重复节点的情况。
• 树剖的常数较小，也可以使用倍增法实现 LCA，但在本题的输入规模下两种方法都能胜任。

---

总结

本题的核心在于将 管理关系 转化为 树上的祖先关系，进而将问题转化为 求一组节点的 LCA 以及根到 LCA 路径上的最大编号。通过一遍 DFS 预处理路径最大值，配合树剖或倍增快速求 LCA，即可高效回答所有询问。是一道典型的 LCA 应用题，适合用来巩固树上最近公共祖先的多种求法和路径信息的维护技巧。