把管辖关系建成森林: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
形式化题目
编号
:长者管辖自己; - 对
: 管辖 当且仅当 ,即 ,并约定 时 。
给定
约束:
关于
正解
思路
第一步:
先看
引理. 同一个
中任意两个球长可以比较:若 ,则 管辖 与 管辖 至少有一个成立。
反证:取"同时管辖两个不可比球长"的最小下标
于是把管辖关系画成偏序的 Hasse 图(只连"直接管辖"的边,即把每个点连向
第二步:
有了森林,
若
又因为
第三步:询问 = 若干条根路径的并。
把询问的点集
它的来源是:
以题面样例为例:名单与建出的森林如下。
| 1 | 无(树根) | 0 | ||
| 2 | 1 | 1 | ||
| 3 | 1 | 1 | ||
| 4 | 2 | 2 | ||
| 5 | 1 | |||
| 6 | 无(新树根) | 0 | ||
| 7 | 2 与 6 不同树 ⇒ 新树根 | 0 |
flowchart TD n1["长者 1"] --> n2["长者 2"] n1 --> n3["长者 3"] n1 --> n5["长者 5"] n2 --> n4["长者 4"] n6["长者 6(独立树根)"] n7["长者 7(独立树根)"]
把样例的三个询问代进恒等式,
| 询问 |
按 |
减掉的 |
树棵数 | 答案 | |
|---|---|---|---|---|---|
| 1 | 3 | ||||
| 1 | 3 | ||||
| 1 | 4 |
三个答案与题面输出一致,也能与题面"
代码
Python 版(倍增 LCA + 同一恒等式):
#!/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 + 虚树恒等式):
/**
* 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;
}复杂度
- 时间:建森林时
的元素要逐个与当前集合 LCA 合并,单次倍增 LCA 为 , 共 ;求 一趟迭代 DFS 为 ; 询问按 排序 ,相邻两两求 LCA 。 顶格数据( 、 )实测 C++ 0.35 s / 23.6 MB(限时 2000 ms、限内存 128 MB)。 - 空间:倍增表
( up[18][n+1],规模下约 29 MB)、 森林与 各 ,单个询问的缓冲区 ,均不依赖 。 - 与 C++ 解法的关系:
main.py是同一套算法(森林 + 倍增 LCA + 虚树恒等式), 复杂度同阶;Python 侧常数大,顶格两个点实测约 3.4 s、峰值内存约 96 MB, 在 2000 ms / 128 MB 的限制下有 TLE/MLE 风险,但解法没有降级。
总结
- 把"管辖"看成偏序,
就是链。 一上手不要去想"间接管辖"的闭包,先证明 是链:任意两个被同一人管辖的球长可比,这条引理让 Hasse 图退化成森林, 于是 = 根路径、 = 集合 LCA,两个关键量同时落地。 - 集合 LCA 要逐个合并,不能用
的 。 的元素分属不同树时交集为空 ( 自成一棵新树),同树时也只能把当前 LCA 与新元素两两合并,共 步。 - 建树的次序不是合法 DFS 序。
保证 (parent) 先于儿子出现, 但"哥哥"可能比"叔叔"晚建出来,所以求 必须重新做一次真正的 DFS, 否则虚树恒等式里"同树的点连成一段"这个前提不成立。 - 根路径并的经典恒等式:
排序后 , 一条式子同时处理跨树(不相交、只多一棵树)和同树(减掉重复前缀)两种情形。 - 数据与来源说明:本题素材源自带数据生成脚本
data.py与自研标程std.cpp, 「采访计划」在公开网络上没有找到题解,的约定也是由样例反推的, 因此题面为网络重建、 data/为自造数据,出题意图与官方原题可能有偏差。 本仓库的main.cpp/main.py都只按上面的模型独立推导实现,另用 「按定义直接求」的暴力在小数据上对拍( 、 含交集与跨树情形、 共 650 组)全部一致,样例也逐行对上;但这不等于官方数据 AC。
