采访计划

GitHub跳转原题关系图返回列表

把管辖关系建成森林:parent(i) = LCA(B_i),管辖集 S_i 就是根到 i 的路径;询问按 DFS 序排序后套虚树恒等式求根路径并大小。

OJ: roj

题目 ID: 1759

难度:提高+/省选-

标签:数据结构树LCA倍增python

创建: 2026-10-07 22:35

更新: 2026-10-07 22:35

形式化题目

编号 1..n1..n 的点同时扮演"长者"和"球长"两个角色,每个点 ii 附一份名单 Bi⊆{1,2,…,i−1}B_i \subseteq \{1, 2, \dots, i-1\}(元素互不重复)。点 ii 管辖的球长集合 SiS_i 由两条规则定出:

  • i∈Sii \in S_i:长者管辖自己;
  • 对 j≠ij \neq i:ii 管辖 jj 当且仅当 ∀k∈Bi, j∈Sk\forall k \in B_i,\ j \in S_k,即 Si={i}∪⋂k∈BiSkS_i = \{i\} \cup \bigcap_{k \in B_i} S_k,并约定 Bi=∅B_i = \varnothing 时 Si={i}S_i = \{i\}。

给定 mm 个询问,第 ii 个询问给出一个长者集合 TiT_i,求 ∣⋃t∈TiSt∣\left| \bigcup_{t \in T_i} S_t \right|——被 TiT_i 中至少一位长者直接或间接管辖的球长个数。

约束:n,m⩽200000n, m \leqslant 200000,∑∣Bi∣⩽2000000\sum |B_i| \leqslant 2000000,询问的 ∑szi⩽2000000\sum sz_i \leqslant 2000000。

关于 Bi=∅B_i = \varnothing 的约定。 若把 Bi=∅B_i = \varnothing 当成"条件空真"(ii 管辖所有球长), 则样例里长者 1 会管辖全部 7 个球长,S2={2}∪S1S_2 = \{2\} \cup S_1 也就成了全集, 询问 {2,3}\{2,3\} 的答案会是 7 而不是样例声明的 3。所以"空名单"只能理解为 Si={i}S_i = \{i\}, 这也与题面"长者管辖自己"一句一致。

正解

思路

第一步:SiS_i 是链,管辖关系是一片森林。

先看 SiS_i 内部的结构。管辖关系自反(ii 管辖 ii)、传递(ii 管辖 jj、jj 管辖 ll 时对 max⁡(i,j)\max(i,j) 归纳即可得 ii 管辖 ll),且显然有 ii 管辖 j⇒i⩾jj \Rightarrow i \geqslant j。

引理. 同一个 SiS_i 中任意两个球长可以比较:若 a,b∈Sia, b \in S_i,则 aa 管辖 bb 与 bb 管辖 aa 至少有一个成立。

反证:取"同时管辖两个不可比球长"的最小下标 ii。由 i⩾ji \geqslant j 知这两个球长都不等于 ii, 故 Bi≠∅B_i \neq \varnothing;又由传递性,每个 k∈Bik \in B_i 也都同时管辖这两个球长,而 k<ik < i, 与 ii 的最小性矛盾。

于是把管辖关系画成偏序的 Hasse 图(只连"直接管辖"的边,即把每个点连向 SiS_i 中除自己外 最大的那个点),每个点至多有一个前驱,图形就是一片森林,而 SiS_i 恰好是森林中从根到 ii 的整条路径。

第二步:parent(i)=Biparent(i) = B_i 的集合 LCA。

有了森林,Si={i}∪⋂k∈BiSkS_i = \{i\} \cup \bigcap_{k \in B_i} S_k 里的交集就是"若干条根路径的公共部分": BiB_i 中的点同在一棵树里时,交集是根到它们集合 LCA 的路径,于是

parent(i)=max⁡(⋂k∈BiSk)=LCA⁡(Bi);parent(i) = \max\left(\bigcap_{k \in B_i} S_k\right) = \operatorname{LCA}(B_i);

若 BiB_i 中的点分属不同的树(交集空)或 BiB_i 为空,则 ii 自成一棵新树的根。

又因为 Bi⊆{1,…,i−1}B_i \subseteq \{1, \dots, i-1\},按 ii 递增处理时 BiB_i 的点早已就位, 新点只会作为叶子挂到已有点下面,已有结点的祖先关系不会变, 所以可以边建森林边把倍增表一起维护好,逐个用 LCALCA 合并 BiB_i 的元素即可求出 parent(i)parent(i)。

第三步:询问 = 若干条根路径的并。

把询问的点集 TT 按真正的 DFS 先序 dfndfn 排序(注意:按 ii 递增建树的次序只是拓扑序, 不是合法 DFS 序——父亲 2 的儿子 4 会因为 4>34 > 3 排在叔叔 3 的后面),排序后同一棵树的点连成一段。 逐条加入根路径,有恒等式

∣⋃t∈Trootpath(t)∣=∑t∈Tdep(t)−∑相邻且同树dep(LCA⁡(tj−1,tj))+(涉及的树棵数).\left| \bigcup_{t \in T} \text{rootpath}(t) \right| = \sum_{t \in T} dep(t) - \sum_{\text{相邻且同树}} dep\big(\operatorname{LCA}(t_{j-1}, t_j)\big) + (\text{涉及的树棵数}).

它的来源是:dfndfn 序下相邻的两点"关系最近",第 jj 条根路径与前面所有路径的并集的公共部分 恰好是 rootpath(LCA⁡(tj−1,tj))\text{rootpath}\big(\operatorname{LCA}(t_{j-1}, t_j)\big),这段前缀在前面已经数过一遍, 减掉 dep(LCA⁡)dep(\operatorname{LCA}) 即可;跨树的两条路径不相交,只把"树棵数"多计一次, 最后每棵树的根(dep=0dep = 0)补上。

以题面样例为例:名单与建出的森林如下。

ii BiB_i parent(i)parent(i) dep(i)dep(i) SiS_i
1 ∅\varnothing 无(树根) 0 {1}\{1\}
2 {1}\{1\} 1 1 {1,2}\{1,2\}
3 {1}\{1\} 1 1 {1,3}\{1,3\}
4 {2}\{2\} 2 2 {1,2,4}\{1,2,4\}
5 {2,3}\{2,3\} LCA⁡(2,3)=1\operatorname{LCA}(2,3)=1 1 {1,5}\{1,5\}
6 ∅\varnothing 无(新树根) 0 {6}\{6\}
7 {2,6}\{2,6\} 2 与 6 不同树 ⇒ 新树根 0 {7}\{7\}
flowchart TD
  n1["长者 1"] --> n2["长者 2"]
  n1 --> n3["长者 3"]
  n1 --> n5["长者 5"]
  n2 --> n4["长者 4"]
  n6["长者 6(独立树根)"]
  n7["长者 7(独立树根)"]

把样例的三个询问代进恒等式,dfndfn 序为 1,5,3,2,4,6,71,5,3,2,4,6,7:

询问 TT 按 dfndfn 排序后 ∑dep\sum dep 减掉的 ∑dep(LCA)\sum dep(\text{LCA}) 树棵数 答案
{2,3}\{2,3\} 3,23,2 1+1=21+1=2 LCA⁡(3,2)=1\operatorname{LCA}(3,2)=1,减 0 1 3
{3,5}\{3,5\} 5,35,3 1+1=21+1=2 LCA⁡(5,3)=1\operatorname{LCA}(5,3)=1,减 0 1 3
{4,5}\{4,5\} 5,45,4 1+2=31+2=3 LCA⁡(5,4)=1\operatorname{LCA}(5,4)=1,减 0 1 4

三个答案与题面输出一致,也能与题面"{4,5}\{4,5\} 可以采访 1,2,4,51,2,4,5"的说明对上 (S4={1,2,4}S_4 = \{1,2,4\}、S5={1,5}S_5 = \{1,5\})。

代码

Python 版(倍增 LCA + 同一恒等式):

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 22:29
# update_at: 2026-10-07 22:29

import sys
from typing import BinaryIO

LOGN = 18  # n <= 2e5 < 2^18,倍增表跳 0..2^17 步就够(深度差最大 199999)

# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type UpTable = list[list[int]]   # 倍增祖先表:up[j][u] 是 u 往上跳 2^j 步的祖先
type Kids = list[list[int]]      # 孩子表:kids[u] 是 u 的所有儿子
type Forest = tuple[list[int], list[int], list[int], UpTable]  # (父亲, 深度, 树根, 倍增表)


def read_entity(fin: BinaryIO) -> list[int]:
    """读一个实体的完整数字:第 0 个是元素个数,后面是元素本身。

    题面保证每个实体占一行,整行切分最快(一次 read().split() 要给本题顶格点的
    440 万个 token 逐个建对象、实测 268 MB,超过 128 MB 内存限制);
    万一某行被换行截断,就继续读下一行补齐。
    """
    nums = list(map(int, fin.readline().split()))
    size = nums[0]
    while len(nums) < size + 1:
        nums += map(int, fin.readline().split())
    return nums


def lca(a: int, b: int, dep: list[int], up: UpTable) -> int:
    """求森林中同树两点的最近公共祖先(调用方保证 a、b 在同一棵树里)。"""
    if dep[a] < dep[b]:
        a, b = b, a
    diff = dep[a] - dep[b]
    j = 0
    while diff:  # 先把 a 抬到与 b 同深度
        if diff & 1:
            a = up[j][a]
        diff >>= 1
        j += 1
    if a == b:
        return a
    for j in range(LOGN - 1, -1, -1):  # 两点一起往上跳,停在 LCA 的两个儿子上
        row = up[j]
        if row[a] != row[b]:
            a, b = row[a], row[b]
    return up[0][a]


def build_forest(fin: BinaryIO, n: int) -> Forest:
    """读入 n 份名单,建出管辖森林,返回 (父亲, 深度, 树根, 倍增表)。

    由 S_i = {i} ∪ (⋂_{k∈B_i} S_k) 得 parent(i) = B_i 全部点的集合 LCA:
    B_i 的点同树时新点挂在集合 LCA 下面,B_i 为空或点分属不同树(交集为空)时
    i 自成一棵新树的根。B_i 的元素都小于 i,按 i 递增建树时它们已经就位,
    新点只会作为叶子挂上去,已有点的祖先关系不变,所以倍增表可以同步建好。
    """
    par = [0] * (n + 1)
    dep = [0] * (n + 1)
    root = [0] * (n + 1)
    up: UpTable = [[0] * (n + 1) for _ in range(LOGN)]
    for i in range(1, n + 1):
        line = read_entity(fin)
        size = line[0]
        cur = 0           # B_i 中已合并部分的集合 LCA
        cross = False     # B_i 的点是否分属不同树
        for j in range(1, size + 1):
            k = line[j]
            if j == 1:
                cur = k
            elif not cross:
                if root[k] != root[cur]:
                    cross = True  # 交集为空,i 只能自成一棵新树
                else:
                    cur = lca(cur, k, dep, up)  # 集合 LCA 只能相邻两点逐个合并
        if size and not cross:  # S_i = {i} ∪ (根 -> LCA(B_i) 的路径)
            par[i] = cur
            dep[i] = dep[cur] + 1
            root[i] = root[cur]
        else:                   # S_i = {i}
            root[i] = i
        up[0][i] = par[i]
        for j in range(1, LOGN):
            up[j][i] = up[j - 1][up[j - 1][i]]
    return par, dep, root, up


def assign_dfn(par: list[int], n: int) -> list[int]:
    """做一次真正的 DFS,求先序编号 dfn:同一棵子树内的点编号连续。

    按 i 递增建树的次序不是合法 DFS 序(父亲 2 的儿子 4 会因为 4 > 3 排在叔伯 3 后面),
    而虚树恒等式要求"同树的点排序后连成一段",所以这里必须重新 DFS 一次。
    """
    kids: Kids = [[] for _ in range(n + 1)]
    for i in range(2, n + 1):
        if par[i]:
            kids[par[i]].append(i)
    dfn = [0] * (n + 1)
    timer = 0
    for r in range(1, n + 1):
        if par[r]:
            continue
        stack = [r]
        while stack:
            u = stack.pop()
            timer += 1
            dfn[u] = timer
            stack.extend(kids[u])  # 儿子整体入栈,出栈次序仍构成合法的先序遍历
    return dfn


def answer_query(nodes: list[int], dep: list[int], root: list[int],
                 dfn: list[int], up: UpTable) -> int:
    """一个询问的答案:Σdep - Σdep(LCA 相邻同树点) + 涉及的树棵数。

    长者 i 管辖的球长就是森林里"根 -> i"这条路径上的点,于是询问在求若干条根路径的
    并集大小。点按 DFS 序排序后同树的点连成一段:相邻两项的公共前缀被算了两次,
    减掉一次;跨树的相邻两项不相交,只把"树棵数"多计一次。
    """
    if not nodes:
        return 0  # 空询问:没有球长被采访
    nodes.sort(key=dfn.__getitem__)  # 按 DFS 序排序,同一棵树的点连成一段
    total = dep[nodes[0]]
    trees = 1
    for i in range(1, len(nodes)):
        u = nodes[i - 1]
        v = nodes[i]
        total += dep[v]
        if root[u] != root[v]:
            trees += 1
        else:
            total -= dep[lca(u, v, dep, up)]
    return total + trees  # 每棵树的根(深度 0)在最浅处只算一次


def solve() -> None:
    fin = sys.stdin.buffer
    n = int(fin.readline())
    par, dep, root, up = build_forest(fin, n)
    dfn = assign_dfn(par, n)

    m = int(fin.readline())
    out: list[int] = []
    for _ in range(m):
        row = read_entity(fin)
        size = row[0]  # 本询问给的长者个数
        out.append(answer_query(row[1:1 + size], dep, root, dfn, up))

    sys.stdout.write('\n'.join(map(str, out)) + '\n')


if __name__ == "__main__":
    solve()

C++ 版(同一算法:森林 + 倍增 LCA + 虚树恒等式):

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 22:29
 * update_at: 2026-10-07 22:29
 */
// main.cpp:一本通 1759《采访计划》。
// 把"管辖"关系建成一片森林:parent(i) = B_i 所有点的集合 LCA(不同树则 i 自成一棵新树),
// 长者 i 管辖的球长集合 S_i 恰好是森林里"根 -> i"这条路径上的全部点。
// 询问即求若⼲条根路径的并集大小:按 DFS 序排序后套虚树恒等式
//     |∪ 根路径| = Σ dep(v) - Σ dep(LCA(相邻同树点)) + (涉及的树棵数)。
// 与 main.py 是同一算法、同一复杂度。

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

typedef long long ll;

const int MAXN = 200005;       // n, m <= 2e5
const int LOGN = 19;           // 2^18 = 262144 > 2e5,倍增表开 19 层留冗余
const int MAXQ = 2000005;      // 单个询问的元素数 <= Σsz <= 2e6

// 森林结点:par / dep / root / dfn 都是同一个点的属性,聚合成一个 struct
struct Node {
    int par;   // 森林中的直接父亲,0 表示它是所在树的根
    int dep;   // 深度,根为 0
    int root;  // 所在树的树根编号(编号等于树根,用于判断两点是否同树)
    int dfn;   // 真正的 DFS 先序编号,同一棵树内的点连续
};
Node node[MAXN];

int up[LOGN][MAXN];   // 倍增祖先表:up[j][u] 是 u 往上跳 2^j 步的祖先,根往上为 0
int head[MAXN];       // 孩子链表的头指针(链式前向星,只存每个点的一个孩子)
int nxt[MAXN];        // 同一父亲的下一个兄弟
int stk[MAXN];        // 迭代 DFS 的手写栈,避免链状树递归爆栈
int qbuf[MAXQ];       // 一个询问里的全部长者编号

// ------------------------------- 快速读入 -------------------------------
static char ibuf[1 << 20];
static size_t ipos = 0, ilen = 0;   // 缓冲区下标与已读长度,用 size_t 与 fread 的返回值对齐

inline int gc() {
    if (ipos == ilen) {
        ilen = fread(ibuf, 1, sizeof(ibuf), stdin);
        ipos = 0;
        if (ilen == 0) return -1;   // 输入读完了
    }
    return ibuf[ipos++];            // 输入只有数字与空白,char 转 int 不会出问题
}

inline int read_int() {
    int c = gc();
    while (c != -1 && (c < '0' || c > '9')) c = gc();
    int x = 0;
    while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = gc(); }
    return x;
}

// ------------------------------- 快速输出 -------------------------------
static char obuf[1 << 20];
static size_t opos = 0;

inline void put_char(char c) {
    if (opos == sizeof(obuf)) { fwrite(obuf, 1, opos, stdout); opos = 0; }
    obuf[opos++] = c;
}

// 答案最大可达 Σdep ≈ 4e11,必须用 ll 输出
inline void write_ll(ll x) {
    char t[24];
    int k = 0;
    if (x == 0) t[k++] = '0';
    while (x > 0) {
        int d = x % 10;              // 收窄成 int,取值 0..9
        t[k++] = '0' + d;            // int 自动转 char 写入缓冲区
        x /= 10;
    }
    while (k > 0) put_char(t[--k]);
    put_char('\n');
}

// 求森林中两点的 LCA。保证调用时两点同树(深度差不为负)。
int lca(int a, int b) {
    if (node[a].dep < node[b].dep) swap(a, b);
    int d = node[a].dep - node[b].dep;
    for (int j = 0; d; ++j, d >>= 1) {          // 先把 a 抬到与 b 同深度
        if (d & 1) a = up[j][a];
    }
    if (a == b) return a;
    for (int j = LOGN - 1; j >= 0; --j) {       // 两个点一起往上跳,跳到 LCA 的儿子
        if (up[j][a] != up[j][b]) { a = up[j][a]; b = up[j][b]; }
    }
    return node[a].par;
}

// 询问里的点数按 DFS 序排序:排序后每一棵树的点各自连成一段
bool cmp_dfn(int a, int b) {
    return node[a].dfn < node[b].dfn;
}

int main() {
    int n = read_int();
    for (int i = 1; i <= n; ++i) {
        int sz = read_int();
        int cur = 0;             // B_i 中已合并部分的集合 LCA
        bool cross = false;      // B_i 的点分属不同树 ⇒ 交集为空 ⇒ i 自成一棵新树
        for (int j = 0; j < sz; ++j) {
            int k = read_int();
            if (j == 0) { cur = k; continue; }      // B_i 里的点都小于 i,必然已经建好
            if (cross) continue;                    // 已经判定跨树,剩下的点只需读完
            if (node[k].root != node[cur].root) { cross = true; continue; }
            cur = lca(cur, k);                      // 集合 LCA 只能相邻两点逐个合并
        }
        if (sz == 0 || cross) {     // S_i = {i}:i 是一棵新树的根
            node[i].par = 0;
            node[i].dep = 0;
            node[i].root = i;
        } else {                    // S_i = {i} ∪ (根 -> LCA(B_i) 的路径)
            node[i].par = cur;
            node[i].dep = node[cur].dep + 1;
            node[i].root = node[cur].root;
        }
        up[0][i] = node[i].par;
        for (int j = 1; j < LOGN; ++j) up[j][i] = up[j - 1][up[j - 1][i]];
        if (node[i].par) { nxt[i] = head[node[i].par]; head[node[i].par] = i; }
    }

    // 求真正的 DFS 先序:按 1..n 的顺序处理树根,每棵子树内的 dfn 连续
    int timer = 0;
    for (int i = 1; i <= n; ++i) {
        if (node[i].par) continue;
        int top = 0;
        stk[top++] = i;
        while (top) {
            int u = stk[--top];
            node[u].dfn = ++timer;
            for (int c = head[u]; c; c = nxt[c]) stk[top++] = c;
        }
    }

    int m = read_int();
    for (int qi = 0; qi < m; ++qi) {
        int sz = read_int();
        for (int j = 0; j < sz; ++j) qbuf[j] = read_int();
        if (sz == 0) { write_ll(0); continue; }     // 空询问:没有任何球长被采访
        sort(qbuf, qbuf + sz, cmp_dfn);
        ll ans = node[qbuf[0]].dep;     // 第一条根路径的长度(不含根,故直接用 dep)
        int trees = 1;                  // 涉及的树棵数,DFS 序下同树的点必连续
        for (int j = 1; j < sz; ++j) {
            int u = qbuf[j - 1], v = qbuf[j];
            ans += node[v].dep;
            if (node[u].root != node[v].root) trees++;      // 跨树:两段根路径不相交
            else ans -= node[lca(u, v)].dep;                // 同树:减去重复计数的公共前缀
        }
        ans += trees;                   // 每棵树的根在最浅处只算一次
        write_ll(ans);
    }

    if (opos) fwrite(obuf, 1, opos, stdout);
    return 0;
}

复杂度

  • 时间:建森林时 BiB_i 的元素要逐个与当前集合 LCA 合并,单次倍增 LCA 为 O(log⁡n)O(\log n), 共 O ⁣(∑∣Bi∣log⁡n)O\!\left(\sum |B_i| \log n\right);求 dfndfn 一趟迭代 DFS 为 O(n)O(n); 询问按 dfndfn 排序 O(∑szilog⁡szi)O(\sum sz_i \log sz_i),相邻两两求 LCA O(∑szilog⁡n)O(\sum sz_i \log n)。 顶格数据(n=m=2×105n = m = 2 \times 10^5、∑∣B∣=∑sz=2×106\sum|B| = \sum sz = 2 \times 10^6)实测 C++ 0.35 s / 23.6 MB(限时 2000 ms、限内存 128 MB)。
  • 空间:倍增表 O(nlog⁡n)O(n \log n)(up[18][n+1],2×1052 \times 10^5 规模下约 29 MB)、 森林与 dfndfn 各 O(n)O(n),单个询问的缓冲区 O(max⁡szi)O(\max sz_i),均不依赖 mm。
  • 与 C++ 解法的关系:main.py 是同一套算法(森林 + 倍增 LCA + 虚树恒等式), 复杂度同阶;Python 侧常数大,顶格两个点实测约 3.4 s、峰值内存约 96 MB, 在 2000 ms / 128 MB 的限制下有 TLE/MLE 风险,但解法没有降级。

总结

  • 把"管辖"看成偏序,SiS_i 就是链。 一上手不要去想"间接管辖"的闭包,先证明 SiS_i 是链:任意两个被同一人管辖的球长可比,这条引理让 Hasse 图退化成森林, 于是 SiS_i = 根路径、parent(i)parent(i) = 集合 LCA,两个关键量同时落地。
  • 集合 LCA 要逐个合并,不能用 dfndfn 的 min⁡/max⁡\min / \max。 BiB_i 的元素分属不同树时交集为空 (ii 自成一棵新树),同树时也只能把当前 LCA 与新元素两两合并,共 O(log⁡n)O(\log n) 步。
  • 建树的次序不是合法 DFS 序。 Bi⊆{1,…,i−1}B_i \subseteq \{1, \dots, i-1\} 保证 (parent) 先于儿子出现, 但"哥哥"可能比"叔叔"晚建出来,所以求 dfndfn 必须重新做一次真正的 DFS, 否则虚树恒等式里"同树的点连成一段"这个前提不成立。
  • 根路径并的经典恒等式:dfndfn 排序后 ∑dep−∑dep(LCA 相邻同树点)+树棵数\sum dep - \sum dep(\text{LCA 相邻同树点}) + \text{树棵数}, 一条式子同时处理跨树(不相交、只多一棵树)和同树(减掉重复前缀)两种情形。
  • 数据与来源说明:本题素材源自带数据生成脚本 data.py 与自研标程 std.cpp, 「采访计划」在公开网络上没有找到题解,Bi=∅B_i = \varnothing 的约定也是由样例反推的, 因此题面为网络重建、data/ 为自造数据,出题意图与官方原题可能有偏差。 本仓库的 main.cpp / main.py 都只按上面的模型独立推导实现,另用 「按定义直接求 ⋂Sk\bigcap S_k」的暴力在小数据上对拍(n⩽80n \leqslant 80、BiB_i 含交集与跨树情形、 共 650 组)全部一致,样例也逐行对上;但这不等于官方数据 AC。