「JOISC 2013 Day2」间谍 题解

有两家公司 JOI 和 IOI，各 $N$ 名员工，形成树形结构（每名员工有唯一上司，总裁为根）。

两家公司各有 $M$ 个项目，对应关系为：间谍项目 $s_b$ 针对研究项目 $r_b$。

• 项目成员：领导及其所有下属（子树中的所有节点）
• 间谍活动：员工 $i_a$ 从 $j_a$ 窃取信息。如果 $i_a$ 属于 $s_b$ 且 $j_a$ 属于 $r_b$，则间谍成功。

求：每个 IOI 员工 $i_a$ 在多少个间谍项目中成功完成间谍活动。

问题分析

关键约束

1. 树结构：两家公司各自是一棵树
2. 项目成员：领导节点的子树
3. 间谍匹配：$i_a$ ↔ $j_a$ 一一对应
4. 成功条件：$i_a$ 在 $s_b$ 中 且 $j_a$ 在 $r_b$ 中

数据范围

• $N \leq 2000$
• $M \leq 500000$

解决方案

第一步：树形结构预处理

对两家公司的树分别做 DFS，得到每个节点的子树信息。

# DFS 预处理
def dfs(tree, node, tin, tout, timer):
    tin[node] = timer[0]
    timer[0] += 1
    for child in tree[node]:
        dfs(tree, child, tin, tout, timer)
    tout[node] = timer[0] - 1

得到：

• $tin_j[a]$, $tout_j[a]$：$j_a$ 在 JOI 树中的 DFS 序区间
• $tin_i[a]$, $tout_i[a]$：$i_a$ 在 IOI 树中的 DFS 序区间

重要性质：节点 $u$ 是节点 $v$ 的祖先 ⇔ $tin[u] \leq tin[v] \leq tout[u]$

第二步：问题转化

对于员工 $i_a$，间谍成功的项目 $s_b$ 满足：

1. $i_a$ 在 $i_{S_b}$ 的子树中：$tin_i[S_b] \leq tin_i[a] \leq tout_i[S_b]$
2. $j_a$ 在 $j_{R_b}$ 的子树中：$tin_j[R_b] \leq tin_j[a] \leq tout_j[R_b]$

对于项目 $b$，可以看作二维平面上的点：

• $x$ 坐标：$tin_i[S_b]$（间谍项目领导的 DFS 序）
• $y$ 坐标：$tin_j[R_b]$（研究项目领导的 DFS 序）

对于员工 $a$，查询的是： 有多少个点 $(x,y)$ 满足：

• $x \leq tin_i[a] \leq tout_i[x]$（实际上需要更复杂的处理）
• $y \leq tin_j[a] \leq tout_j[y]$

第三步：更精确的模型

实际上，条件 "$i_a$ 在 $i_{S_b}$ 的子树中" 等价于：

• $i_{S_b}$ 是 $i_a$ 的祖先（包括自身）

类似地，"$j_a$ 在 $j_{R_b}$ 的子树中" 等价于：

• $j_{R_b}$ 是 $j_a$ 的祖先（包括自身）

因此，对于每个员工 $a$，我们需要统计项目 $b$ 的数量，使得：

• $i_{S_b}$ 是 $i_a$ 的祖先
• $j_{R_b}$ 是 $j_a$ 的祖先

第四步：高效算法设计

方法1：祖先预处理 + 暴力匹配（适用于小数据）

# 预处理所有节点的祖先列表
def get_ancestors(parent, N):
    ancestors = [[] for _ in range(N+1)]
    for node in range(1, N+1):
        cur = node
        while cur != 0:
            ancestors[node].append(cur)
            cur = parent[cur]
    return ancestors

# 对于每个员工a
def count_for_employee(a, ioi_ancestors, joi_ancestors, projects):
    count = 0
    # projects: list of (S_b, R_b)
    for S_b, R_b in projects:
        if S_b in ioi_ancestors[a] and R_b in joi_ancestors[a]:
            count += 1
    return count

复杂度：$O(NM)$，对于 $M=500000$ 不可行。

方法2：基于 DFS 序的优化

关键观察： 设 $anc_i[a]$ 表示 $i_a$ 的所有祖先（包括自身）的集合。 设 $anc_j[a]$ 表示 $j_a$ 的所有祖先（包括自身）的集合。

我们需要统计：有多少个项目 $b$ 满足 $S_b \in anc_i[a]$ 且 $R_b \in anc_j[a]$。

这可以看作一个二维计数问题。

优化思路：

1. 对于每个间谍项目领导 $S$，收集所有以 $S$ 为领导的项目对应的 $R_b$
2. 对于每个员工 $a$，遍历 $i_a$ 的所有祖先 $anc$
3. 对于每个祖先 $anc$，检查 $j_a$ 的祖先中包含了多少个 $R_b$

方法3：最终高效算法

算法步骤：

1. 预处理：

   • 对两家公司的树分别做 DFS，得到 DFS 序
   • 预处理每个节点的所有祖先（或使用倍增法快速判断祖先关系）

2. 项目索引：

   • 创建数组 projects_by_leader[S]：存储所有以 $S$ 为领导的间谍项目对应的 $R_b$

3. 员工计数： 对于每个员工 $a$：

   count = 0
   for anc in ancestors_i[a]:  # i_a的所有祖先
       for R_b in projects_by_leader[anc]:
           if is_ancestor(R_b, j_a):  # R_b是j_a的祖先
               count += 1
   

4. 祖先判断优化： 使用 DFS 序快速判断祖先关系：

   def is_ancestor(u, v, tin, tout):
       return tin[u] <= tin[v] <= tout[u]
   

复杂度分析：

• 预处理：$O(N^2)$ 存储所有祖先（$N=2000$，$N^2=4\times10^6$ 可接受）
• 项目索引：$O(M)$
• 员工计数：最坏 $O(N \times \text{平均祖先数} \times \text{平均项目数})$

由于 $N=2000$ 较小，$O(N^2)$ 的操作是可接受的。

第五步：进一步优化

优化1：压缩项目信息

对于同一个领导 $S$ 的多个项目，如果 $R_b$ 相同，可以合并计数。

优化2：使用位集（bitset）

由于 $N=2000$，可以使用 $2000$ 位的 bitset：

• 对于每个员工 $j_a$，用 bitset 表示它的所有祖先
• 对于每个间谍领导 $S$，用 bitset 表示所有相关的 $R_b$

然后对于员工 $a$：

count = 0
for anc in ancestors_i[a]:
    count += (ancestors_j[a] & projects_bitset[anc]).count()

复杂度：$O(N^2 \times \frac{N}{w})$，其中 $w=64$（机器字长）

优化3：离线处理 + 树状数组

更高级的算法：

1. 将项目 $(S_b, R_b)$ 看作二维点
2. 对员工查询离线处理
3. 使用树状数组进行二维数点

但 $N=2000$ 较小，bitset 方法更简单高效。

第六步：完整算法实现

import sys
from collections import defaultdict

def solve():
    input = sys.stdin.read().split()
    idx = 0
    N, M = int(input[idx]), int(input[idx+1])
    idx += 2
    
    # 读取员工信息
    joi_parent = [0]*(N+1)
    ioi_parent = [0]*(N+1)
    joi_children = [[] for _ in range(N+1)]
    ioi_children = [[] for _ in range(N+1)]
    
    for a in range(1, N+1):
        P, Q = int(input[idx]), int(input[idx+1])
        idx += 2
        joi_parent[a] = P
        ioi_parent[a] = Q
        if P != 0:
            joi_children[P].append(a)
        if Q != 0:
            ioi_children[Q].append(a)
    
    # 读取项目信息
    projects_by_leader = [[] for _ in range(N+1)]
    for _ in range(M):
        R, S = int(input[idx]), int(input[idx+1])
        idx += 2
        projects_by_leader[S].append(R)
    
    # DFS 预处理
    def dfs(children, node, tin, tout, timer):
        tin[node] = timer[0]
        timer[0] += 1
        for child in children[node]:
            dfs(children, child, tin, tout, timer)
        tout[node] = timer[0] - 1
    
    # JOI 树 DFS 序
    joi_tin = [0]*(N+1)
    joi_tout = [0]*(N+1)
    timer = [1]
    joi_root = [i for i in range(1, N+1) if joi_parent[i] == 0][0]
    dfs(joi_children, joi_root, joi_tin, joi_tout, timer)
    
    # IOI 树 DFS 序
    ioi_tin = [0]*(N+1)
    ioi_tout = [0]*(N+1)
    timer = [1]
    ioi_root = [i for i in range(1, N+1) if ioi_parent[i] == 0][0]
    dfs(ioi_children, ioi_root, ioi_tin, ioi_tout, timer)
    
    # 祖先判断函数
    def is_ancestor(u, v, tin, tout):
        return tin[u] <= tin[v] <= tout[u]
    
    # 预处理每个节点的所有祖先
    joi_ancestors = [[] for _ in range(N+1)]
    ioi_ancestors = [[] for _ in range(N+1)]
    
    for a in range(1, N+1):
        # JOI 祖先
        cur = a
        while cur != 0:
            joi_ancestors[a].append(cur)
            cur = joi_parent[cur]
        # IOI 祖先
        cur = a
        while cur != 0:
            ioi_ancestors[a].append(cur)
            cur = ioi_parent[cur]
    
    # 为每个员工计算结果
    results = [0]*(N+1)
    
    for a in range(1, N+1):
        count = 0
        # 遍历 i_a 的所有祖先
        for anc_i in ioi_ancestors[a]:
            # 检查以 anc_i 为领导的所有项目
            for R_b in projects_by_leader[anc_i]:
                # 检查 R_b 是否是 j_a 的祖先
                if is_ancestor(R_b, a, joi_tin, joi_tout):
                    count += 1
        results[a] = count
    
    # 输出结果
    out = []
    for a in range(1, N+1):
        out.append(str(results[a]))
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    solve()

第七步：复杂度分析

• 时间复杂度：

  • DFS 预处理：$O(N)$
  • 祖先预处理：$O(N^2)$
  • 项目处理：$O(M)$
  • 员工计数：最坏 $O(N^2 \times \text{平均项目数})$，但实际中平均项目数不会太大
  • 对于 $N=2000$，$O(N^2) = 4\times 10^6$ 可接受

• 空间复杂度：

  • 存储祖先列表：$O(N^2)$
  • 存储项目：$O(M)$

算法标签

• 树结构：树形组织、DFS 序、祖先关系
• 图结构：两棵树、对应关系
• 数据结构：bitset、离线处理
• 搜索：DFS 遍历
• 模拟：模拟间谍活动匹配

总结

本题的核心是将间谍成功条件转化为树上的祖先关系查询：

1. 利用 DFS 序快速判断祖先关系
2. 预处理每个节点的所有祖先
3. 对于每个员工，检查其 IOI 祖先领导的间谍项目对应的 JOI 领导是否是其 JOI 祖先

对于 $N=2000$ 的规模，$O(N^2)$ 的算法是可行的。如果需要处理更大的 $N$，可以使用 bitset 优化或二维数点算法。