树上搜索

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

先按权重策略构造与目标无关的二叉决策树，再沿目标类别的答案路径输出问题序列。

OJ: shumeng

题目 ID: CSP202312C

难度:提高+/省选-

标签:树DFS 序决策树前缀和

日期: 2026-07-31 16:21

形式化题目

类别关系是一棵以 1 为根的树，每个类别有一个正权重。反复执行：在当前候选类别集合中选择一个类别 $x$ ，使 $|x$ 子树内候选权重和 $-$ 其余候选权重和 $|$ 最小，编号相同取更小者；根据目标是否属于 $x$ 的子树，保留对应部分。直到只剩一个类别。对 $m$ 个给定目标类别，输出整个提问序列。

思路

先看每个状态重新枚举候选子树节点的朴素程序，它在 $n$ 较大时较慢，但逻辑直接：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109/**
 * 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-07-31 16:21
 * update_at: 2026-08-17 22:40
 */
// brute.cpp：小数据暴力解，每个状态重新枚举候选子树中的所有节点。
#include <bits/stdc++.h>
using namespace std;

struct DecisionNode {
    int question, yes_child, no_child;
};

int n, m, timer_count;
vector<long long> weight;
vector<int> tin, tout;
vector<vector<int> > child;
vector<DecisionNode> decision;

void dfs(int node) {
    tin[node] = ++timer_count;
    for (int i = 0; i < (int)child[node].size(); i++) dfs(child[node][i]);
    tout[node] = timer_count;
}

bool in_subtree(int node, int root) {
    return tin[root] <= tin[node] && tin[node] <= tout[root];
}

int build_decision_tree(const vector<char> &active) {
    int active_count = 0;
    for (int i = 1; i <= n; i++) active_count += active[i];
    int current = decision.size();
    decision.push_back({0, -1, -1});
    if (active_count == 1) return current;

    long long total = 0;
    for (int i = 1; i <= n; i++) {
        if (active[i]) total += weight[i];
    }
    long long best_difference = LLONG_MAX;
    int best_question = 0;
    for (int i = 1; i <= n; i++) {
        if (!active[i]) continue;
        long long inside_weight = 0;
        for (int j = 1; j <= n; j++) {
            if (active[j] && in_subtree(j, i)) inside_weight += weight[j];
        }
        long long difference = llabs(total - 2 * inside_weight);
        if (difference < best_difference
                || (difference == best_difference && i < best_question)) {
            best_difference = difference;
            best_question = i;
        }
    }

    vector<char> yes_active(n + 1, 0), no_active(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        if (!active[i]) continue;
        if (in_subtree(i, best_question)) yes_active[i] = 1;
        else no_active[i] = 1;
    }
    decision[current].question = best_question;
    decision[current].yes_child = build_decision_tree(yes_active);
    int no_count = 0;
    for (int i = 1; i <= n; i++) no_count += no_active[i];
    if (no_count > 0) decision[current].no_child = build_decision_tree(no_active);
    return current;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    weight.resize(n + 1);
    for (int i = 1; i <= n; i++) cin >> weight[i];
    child.resize(n + 1);
    for (int i = 2; i <= n; i++) {
        int parent;
        cin >> parent;
        child[parent].push_back(i);
    }
    tin.resize(n + 1);
    tout.resize(n + 1);
    dfs(1);

    vector<char> active(n + 1, 1);
    build_decision_tree(active);
    while (m--) {
        int target;
        cin >> target;
        int current = 0;
        bool first = true;
        while (decision[current].question != 0) {
            int question = decision[current].question;
            if (!first) cout << ' ';
            first = false;
            cout << question;
            if (in_subtree(target, question)) current = decision[current].yes_child;
            else current = decision[current].no_child;
        }
        cout << '\n';
    }

    return 0;
}

所有目标共享同一棵决策树

某个状态中下一次选择哪个类别，只由当前候选集合和权重决定，与目标类别无关。一次提问把候选集合划分为“在问题类别子树内”和“不在子树内”两部分。

因此可以从全集开始构造一棵二叉树：节点保存问题编号和两个答案分支。候选集合只会被不断划分，直到每个叶子对应一个类别。构造完成后，每个测试目标只需沿这棵树走一条路径，无需为每个目标重新模拟。

用 DFS 序计算子树权重

对原树做 DFS，得到 tin 和 tout。节点 $x$ 的子树对应 DFS 序上的连续区间 $[tin_x,tout_x]$ 。

对当前候选集合，把候选节点的权重放在 DFS 序对应位置（非候选为 0），做一次前缀和，就能在 $O(1)$ 求出任意类别子树内的候选权重。扫描所有候选类别即可找到最小差值；差值相同时按编号更小者更新。

复杂度来源

构造一个状态时复制并划分候选集合，决策状态总数不超过 $2n-1$ 个，总复杂度为 $O(n^2)$ ，在 $n\le 2000$ 时可接受。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129/**
 * 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-07-31 16:21
 * update_at: 2026-08-17 22:40
 */
#include <bits/stdc++.h>
using namespace std;

// 决策树节点：question 是要问的类别，yes/no_child 为两个答案分支的节点下标
struct DecisionNode {
    int question;
    int yes_child;
    int no_child;
};

int n, m;
int timer_count;              // DFS 序计数器
vector<long long> weight;     // 每个类别的权重
vector<int> tin, tout;        // 每个节点的 DFS 进入/离开时间戳
vector<vector<int> > child;   // 类别树的子节点列表
vector<DecisionNode> decision; // 决策树

// 对类别树做 DFS，得到每个节点的子树区间 [tin, tout]
void dfs(int node) {
    tin[node] = ++timer_count;
    for (int i = 0; i < (int)child[node].size(); i++) {
        dfs(child[node][i]);
    }
    tout[node] = timer_count;
}

// 判断 node 是否在 root 的子树内（用 DFS 序区间判断）
bool in_subtree(int node, int root) {
    return tin[root] <= tin[node] && tin[node] <= tout[root];
}

// 递归构造决策树：active[i] 表示类别 i 是否还在当前候选集合中。
// 返回新建节点的下标。
int build_decision_tree(const vector<char> &active) {
    int active_count = 0;
    for (int i = 1; i <= n; i++) active_count += active[i];

    int current = decision.size();
    decision.push_back({0, -1, -1});
    if (active_count == 1) return current; // 只剩一个类别，叶子节点

    // 用 DFS 序前缀和计算每个类别子树内的候选权重
    vector<long long> prefix(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        prefix[tin[i]] = active[i] ? weight[i] : 0;
    }
    for (int i = 1; i <= n; i++) prefix[i] += prefix[i - 1];

    // 选出使 |子树权重 - 其余权重| 最小、编号最小的候选类别
    long long total = prefix[n];
    long long best_difference = LLONG_MAX;
    int best_question = 0;
    for (int i = 1; i <= n; i++) {
        if (!active[i]) continue;
        long long inside_weight = prefix[tout[i]] - prefix[tin[i] - 1];
        long long difference = llabs(total - 2 * inside_weight);
        if (difference < best_difference
                || (difference == best_difference && i < best_question)) {
            best_difference = difference;
            best_question = i;
        }
    }

    // 按目标是否在该子树中，把候选集合一分为二
    vector<char> yes_active(n + 1, 0), no_active(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        if (!active[i]) continue;
        if (in_subtree(i, best_question)) yes_active[i] = 1;
        else no_active[i] = 1;
    }

    decision[current].question = best_question;
    decision[current].yes_child = build_decision_tree(yes_active);
    int no_count = 0;
    for (int i = 1; i <= n; i++) no_count += no_active[i];
    if (no_count > 0) decision[current].no_child = build_decision_tree(no_active);
    return current;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    weight.resize(n + 1);
    for (int i = 1; i <= n; i++) cin >> weight[i];

    child.resize(n + 1);
    for (int i = 2; i <= n; i++) {
        int parent;
        cin >> parent;
        child[parent].push_back(i);
    }
    tin.resize(n + 1);
    tout.resize(n + 1);
    dfs(1);

    // 从全集开始一次性构造与目标无关的决策树
    vector<char> active(n + 1, 1);
    decision.reserve(2 * n);
    build_decision_tree(active);

    // 每个测试目标只需沿决策树走一条路径
    while (m--) {
        int target;
        cin >> target;
        int current = 0;
        bool first = true;
        while (decision[current].question != 0) {
            int question = decision[current].question;
            if (!first) cout << ' ';
            first = false;
            cout << question;
            // 目标在子树内走 yes 分支，否则走 no 分支
            if (in_subtree(target, question)) current = decision[current].yes_child;
            else current = decision[current].no_child;
        }
        cout << '\n';
    }

    return 0;
}

复杂度

决策树最多有 $2n-1$ 个状态，每个状态用 $O(n)$ 时间做前缀和、选择问题和划分集合，构造时间复杂度为 $O(n^2)$ 。递归构造中的候选集合最坏为 $O(n^2)$ 空间，决策树与树上辅助数组为 $O(n)$ ，在 $n\le 2000$ 时满足空间限制。每个测试类别输出路径的时间为其问题数。

总结

不要为每个目标类别独立模拟。把“策略如何提问”看成一棵与目标无关的决策树，先一次性构造，再对每个目标读取对应路径；DFS 序前缀和则把每个状态中的子树权重计算降为线性扫描。

题目来自第 32 次 CSP 认证 T3，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 1.0 秒

空间限制： 512 MB

题目背景

西西艾弗岛大数据中心为了收集用于模型训练的数据，推出了一项自愿数据贡献的系统。岛上的居民可以登录该系统，回答系统提出的问题，从而为大数据中心提供数据。为了保证数据的质量，系统会评估回答的正确性，如果回答正确，系统会给予一定的奖励。

近期，大数据中心需要收集一批关于名词分类的数据。系统中会预先设置若干个名词类别，这些名词类别存在一定的层次关系。例如，“动物”是“生物”的次级类别，“鱼类”是“动物”的次级类别，“鸟类”是“动物”的次级类别，“鱼类”和“鸟类”是“动物”下的邻居类别。这些名词类别可以被按树形组织起来，即除了根类别外，每个类别都有且仅有一个上级类别。并且所有的名词都可以被归类到某个类别中，即每个名词都有且仅有一个类别与其对应。一个类别的后代类别的定义是：若该类别没有次级类别，则该类别没有后代类别；否则该类别的后代类别为该类别的所有次级类别，以及其所有次级类别的后代类别。

下图示意性地说明了标有星号的类别的次级类别和后代类别。

系统向用户提出问题的形式是：某名词是否属于某类别，而用户可以选择“是”或“否”来回答问题。该问题的含义是：某名词是否可以被归类到某类别或其后代类别中。

例如，要确定名词“鳕鱼”的类别，系统会向用户提出“鳕鱼是否属于动物”，当用户选择“是”时，系统会进一步询问“鳕鱼是否属于鱼类”，当用户选择“是”时，即可确定“鳕鱼”可以被归类到“鱼类”这一类别。

此外，如果没有更具体的分类，某一名词也可以被归类到非叶子结点的类别中。例如，要确定“猫”的类别，系统可以向用户提出“猫是否属于动物”，当用户选择“是”时，系统会进一步分别询问“猫”是否属于“鱼类”和“鸟类”，当两个问题收到了否定的答案后，系统会确定“猫”的类别是“动物”。

大数据中心根据此前的经验，已经知道了一个名词属于各个类别的可能性大小。为了用尽量少的问题确定某一名词的类别，大数据中心希望小 C 来设计一个方法，以减少系统向用户提出的问题的数量。

题目描述

小 C 观察了事先收集到的数据，并加以统计，得到了一个名词属于各个类别的可能性大小的信息。具体而言，每个类别都可以赋予一个被称为权重的值，值越大，说明一个名词属于该类别的可能性越大。由于每次向用户的询问可以获得两种回答，小 C 联想到了二分策略。他设计的策略如下：

对于每一个类别，统计它和其全部后代类别的权重之和，同时统计其余全部类别的权重之和，并求二者差值的绝对值，计为 $w_{\delta}$ ；
选择 $w_{\delta}$ 最小的类别，如果有多个，则选取编号最小的那一个，向用户询问名词是否属于该类别；
如果用户回答“是”，则仅保留该类别及其后代类别，否则仅保留其余类别；
重复步骤 1，直到只剩下一个类别，此时即可确定名词的类别。

小 C 请你帮忙编写一个程序，来测试这个策略的有效性。你的程序首先读取到所有的类别及其上级次级关系，以及每个类别的权重。你的程序需要测试对于被归类到给定类别的名词，按照上述策略提问，向用户提出的所有问题。

输入格式

从标准输入读入数据。

输入的第一行包含空格分隔的两个正整数 $n$ 和 $m$ ，分别表示全部类别的数量和需要测试的类别的数量。所有的类别从 $1$ 到 $n$ 编号，其中编号为 1 的是根类别。

输入的第二行包含 $n$ 个空格分隔的正整数 $w_1, w_2, \dots, w_n$ ，其中第 $i$ 个数 $w_i$ 表示编号为 $i$ 的类别的权重。

输入的第三行包含 $(n-1)$ 个空格分隔的正整数 $p_2, p_3, \dots, p_n$ ，其中第 $i$ 个数 $p_{i+1}$ 表示编号为 $(i+1)$ 的类别的上级类别的编号，其中 $p_{i} \in [1, n]$

接下来输入 $m$ 行，每行一个正整数，表示需要测试的类别编号。

输出格式

输出 $m$ 行，每行表示对一个被测试的类别的测试结果。表示按小 C 的询问策略，对属于给定的被测类别的名词，需要依次向用户提出的问题。

每行包含若干空格分隔的正整数，每个正整数表示一个问题中包含的类别的编号，按照提问的顺序输出。

input1

1
2
3
4
55 2
10 50 10 10 20
1 1 3 3
5
3

output1

1
22 5
2 5 3 4

样例 1 解释

上述输入数据所表示的类别关系如下图所示，同时各个类别的权重也标注在了图上。

对于归类于类别 5 的某个名词，按照上述询问策略，应当对于树上的每个节点，都计算 $w_{\delta}$ 的值，对于类别 1 至 5，得到的 $w_{\delta}$ 分别为：100、0、20、80、60。因此首先就类别 2 提问。由于类别 5 不属于类别 2 的后代类别，因此用户回答“否”，此时去除类别 2 和其全部后代类别，仅保留类别 1、3、4、5。对于剩下的类别，计算 $w_{\delta}$ 的值，得到的 $w_{\delta}$ 分别为：50、30、30、10。因此再就类别 5 提问。由于类别 5 就是被提问的名词所属类别，因此用户回答“是”，此时仅保留类别 5 和其全部后代类别。我们发现，这个时候，只剩下类别 5，因此算法结束。上述过程如下图所示：

对于归类于类别 3 的某个名词，按照上述询问策略，依次对类别 2、5 提问，过程与前述一致。但是由于类别 3 不属于类别 2 的后代类别，用户回答“否”，此时应当去掉类别 5 和其后代类别，仅保留类别 1、3、4。分别计算 $w_{\delta}$ 得：30、10、10。此时应当选择编号较小的类别 3 提问。由于类别 3 就是被提问的名词所属类别，因此用户回答“是”，此时仅保留类别 3 和其全部后代类别。我们发现，这个时候，并非只剩下一个类别，因此算法还应继续进行。剩下的类别有 3、4，分别计算 $w_{\delta}$ 得：20、0。因此再就类别 4 提问。由于类别 3 不属于类别 4 的后代类别，用户回答“否”，此时应当去掉类别 4 和其后代类别，仅保留类别 3。我们发现，这个时候，只剩下类别 3，因此算法结束。上述过程如下图所示：

子任务

对 $20\%$ 的数据，各个类别的权重相等，且每个类别的上级类别都是根类别；

对另外 $20\%$ 的数据，每个类别的权重相等，且每个类别至多有一个下级类别；

对 $60\%$ 的数据，有 $n \leq 100$ ，且 $m \leq 10$ ；

对 $100\%$ 的数据，有 $n \leq 2000$ ， $m \leq 100$ ，且 $w_i \leq 10^7$ 。

树上搜索

目录

形式化题目

思路

所有目标共享同一棵决策树

用 DFS 序计算子树权重

复杂度来源

代码

复杂度

总结