【CSP-J】树上搜索(问题拆解+方案构建+思考过程)-EW帮帮网

在这篇文章中，我们将详细探讨并解决一个复杂的分类问题。该问题要求通过最优提问策略，以最少的提问次数确定某个名词所属的类别。我们将使用递归树算法来构建和优化这一解决方案。

本文将涵盖以下内容：

问题描述与分析
数据结构与变量说明
解决方案分解与实现
完整的 C++ 代码实现
时间与空间复杂度分析
总结与启发

1. 问题描述与分析

问题背景：我们面临一个分类问题，要求通过系统提出的问题，以最少的提问次数确定某个名词的类别。名词的分类结构为树形，除了根类别外，每个类别都有且仅有一个上级类别。所有名词都可以被归类到某个类别中，系统需要通过判断某个名词是否属于某类别或其子类别来逐步缩小候选范围，最终确定名词的类别。

问题目标：实现最优的提问策略，以最少的提问次数确定名词所属的类别。

功能步骤：

数据输入与树结构构建：读取输入数据，构建树结构，并将所有节点组织成父子关系。
权重计算：递归计算每个节点及其所有子节点的权重和，为后续的提问策略提供数据支持。
最佳提问策略的执行：通过遍历树结构，计算每个节点的权重差值，选择最佳提问节点。
动态调整树结构：根据用户的回答移除或恢复节点，以动态调整树结构。
输出结果：根据最佳提问节点的选择顺序输出最终结果。

2. 数据结构与变量说明

为了解决这个问题，我们设计了一些关键数据结构和变量。

数据结构

struct Node {
    long long Weight;         // 节点自身的权重，表示该类别的可能性大小
    long long WeightSum;      // 节点及其所有子节点的权重和，用于确定最佳提问节点
    long long Index;          // 节点的索引编号，唯一标识每个节点
    bool IsOut;               // 表示节点是否已被移除，主要用于动态调整树结构
    Node* Child;              // 指向第一个子节点的指针，用于遍历子节点
    Node* Brother;            // 指向兄弟节点的指针，用于横向遍历兄弟节点
    Node* Above;              // 指向父节点的指针，用于向上追溯父节点
    Node* LastChild;          // 指向最后一个子节点的指针，便于添加新子节点时快速定位
    Node* PrevBrother;        // 指向前一个兄弟节点的指针，便于在移除节点时调整指针

    // 构造函数，初始化节点信息
    Node(long long Weigh, long long i) : Weight(Weigh), Child(nullptr), LastChild(nullptr), Above(nullptr), Brother(nullptr), WeightSum(Weigh), PrevBrother(nullptr), Index(i) {}
};

变量说明

n：表示类别的总数。用于初始化所有类别的节点。
m：表示需要测试的类别数量。决定了程序中需要进行多少次查询。
Nodes：一个指针数组，用于存储所有节点对象。每个节点都是树中的一个类别。
RemovedParents 和 RemovedChilds：这两个数组分别存储被移除的节点及其父节点，用于在查询结束后恢复树的原始结构。
RemovedPairs：记录被移除的节点对数，便于恢复时使用。
CurMin 和 CurIdx：用于在遍历过程中记录当前找到的最小权重差值及其对应的节点索引，以便选择最佳的提问节点。
CurTotalWeight：当前子树的总权重，用于计算每个节点的权重差值。

3. 解决方案分解与实现

我们将总问题拆解为以下子问题，并逐一分析和解决。

子问题1：数据输入与树结构构建

功能：读取输入数据，初始化节点，并构建父子关系。 算法与知识：基本的输入操作，指针操作。

实现过程中，我们首先需要快速地读取数据，并初始化每个节点。接着，我们将子节点与父节点链接起来，构建出完整的树结构。

子问题2：权重计算

功能：计算每个节点及其所有子节点的权重和。 算法与知识：递归算法，深度优先搜索。

通过递归遍历每个节点的子节点，我们能够计算出每个节点的总权重，这在后续的提问策略中非常关键。

子问题3：最佳提问策略的执行

功能：选择最佳的提问节点，以便通过最少的提问次数锁定目标类别。 算法与知识：动态规划，遍历算法。

我们需要遍历整个树结构，找到权重差值最小的节点作为最佳提问节点。

子问题4：动态调整树结构

功能：根据用户的回答调整树结构，确保剩余候选类别的正确性。 算法与知识：指针操作，树的修剪与恢复。

通过动态调整树结构，我们可以更有效地缩小候选范围，最终确定目标类别。

4. 完整的 C++ 代码实现

以下是完整的代码实现，包含了详细的注释，以帮助理解每一步的原理和作用。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits.h>
using namespace std;

// 快速输入函数，用于高效读取大数据量的输入
inline long long read() {
    long long x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {  // 处理非数字字符，主要是处理负号
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {  // 将连续的数字字符转换为整数
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;  // 返回处理好的整数值
}

// 定义树节点结构体
struct Node {
    long long Weight;         // 节点自身的权重，表示该类别的可能性大小
    long long WeightSum;      // 节点及其所有子节点的权重和，用于确定最佳提问节点
    long long Index;          // 节点的索引编号，唯一标识每个节点
    bool IsOut;               // 表示节点是否已被移除，主要用于动态调整树结构
    Node* Child;              // 指向第一个子节点的指针，用于遍历子节点
    Node* Brother;            // 指向兄弟节点的指针，用于横向遍历兄弟节点
    Node* Above;              // 指向父节点的指针，用于向上追溯父节点
    Node* LastChild;          // 指向最后一个子节点的指针，便于添加新子节点时快速定位
    Node* PrevBrother;        // 指向前一个兄弟节点的指针，便于在移除节点时调整指针

    // 构造函数，初始化节点信息
    Node(long long Weigh, long long i) : Weight(Weigh), Child(nullptr), LastChild(nullptr), Above(nullptr), Brother(nullptr), WeightSum(Weigh), PrevBrother(nullptr), Index(i) {}
};

// 节点数组，保存所有节点
Node* Nodes[2010];

// 将子节点链接到父节点，构建树结构
void LinkNode(Node* Parent, Node* Child) {
    if (!Parent || !Child) return; // 防止空指针操作
    Child->Above = Parent;         // 子节点的父节点设置为 Parent
    if (!Parent->Child) {          // 如果父节点没有子节点
        Parent->Child = Child;     // 设置为第一个子节点
        Parent->LastChild = Child; // 同时也是最后一个子节点
        return;
    }
    Parent->LastChild->Brother = Child; // 否则，链接到兄弟节点
    Child->PrevBrother = Parent->LastChild; // 设置前一个兄弟节点
    Parent->LastChild = Child;   // 更新最后一个子节点为当前子节点
}

// 递归计算每个节点及其所有子节点的权重和
long long AccWeights(Node* CurRoot) {
    if (!CurRoot) return 0;  // 如果当前节点为空，返回0
    CurRoot->WeightSum = CurRoot->Weight;  // 初始化权重和为节点自身的权重
    Node* CurNode = CurRoot->Child;
    while (CurNode) {  // 遍历所有子节点
        CurRoot->WeightSum += AccWeights(CurNode);  // 递归累加子节点的权重和
        CurNode = CurNode->Brother;  // 移动到下一个兄弟节点
    }
    return CurRoot->WeightSum;  // 返回当前节点的总权重和
}

// 检查目标节点是否存在于某个节点的子树中
bool HasTarIndex(Node* Root, long long Tar) {
    if (!Root) return 0;   // 如果节点为空，返回 false
    else if (Root->Index == Tar) return 1;  // 如果找到目标节点，返回 true
    Node* CurNode = Root->Child;
    while (CurNode) {  // 遍历所有子节点
        if (HasTarIndex(CurNode, Tar)) return 1;  // 递归检查子节点
        CurNode = CurNode->Brother;  // 移动到下一个兄弟节点
    }
    return 0;  // 如果没有找到，返回 false
}

// 移除节点并断开其与父节点及兄弟节点的连接
void RemoveNode(Node* TarNode) {
    if (!TarNode) return;  // 防止空指针操作
    if (!TarNode->PrevBrother) TarNode->Above->Child = TarNode->Brother;
    else TarNode->PrevBrother->Brother = TarNode->Brother;
    if (!TarNode->Brother) TarNode->Above->LastChild = TarNode->PrevBrother;
    else TarNode->Brother->PrevBrother = TarNode->PrevBrother;
    TarNode->Above = nullptr;   // 断开父节点的连接
    TarNode->Brother = nullptr; // 断开兄弟节点的连接
    TarNode->PrevBrother = nullptr; // 清空前一个兄弟指针
}

// 用于记录被移除的节点及其父节点的数组
long long RemovedParents[2010]{ -1 }, RemovedChilds[2010]{ -1 };
long long RemovedPairs = 0;

// 恢复之前移除的节点，重建树结构
void ReBuild() {
    for (long long i = 0; i < RemovedPairs; ++i) 
        LinkNode(Nodes[RemovedParents[i]], Nodes[RemovedChilds[i]]);
    RemovedPairs = 0;
}

// 计算某个节点的权重差值
long long GetDelta(Node* TarNode, long long& CurTotalWeight) {
    if (!TarNode) return 114514; // 特殊返回值，表示无效状态
    else if (!TarNode->Above) return TarNode->WeightSum; // 根节点的差值是自身权重和
    return abs(CurTotalWeight - 2 * TarNode->WeightSum); // 计算权重差值
}

// 遍历树结构中的所有节点，找到最佳提问节点
void Bianli(Node* CurRoot, long long& CurTotalWeight, long long& CurMin, long long& CurIdx) {
    if (!CurRoot) return;  // 如果当前节点为空，返回
    long long Delta = GetDelta(CurRoot, CurTotalWeight); // 计算当前节点的权重差值
    if (Delta < CurMin || (CurMin == Delta && CurRoot->Index < CurIdx)) {
        CurMin = Delta;  // 更新最小权重差值
        CurIdx = CurRoot->Index;  // 更新最佳提问节点的索引
    }
    Node* CurNode = CurRoot->Child;
    while (CurNode) {  // 遍历所有子节点
        Bianli(CurNode, CurTotalWeight, CurMin, CurIdx);  // 递归遍历
        CurNode = CurNode->Brother;  // 移动到下一个兄弟节点
    }
}

// 处理每个测试类别的查询过程
int main() {
    long long n = read(), m = read(); // 读取类别总数和测试类别数

    // 初始化节点并读取权重
    for (long long i = 1; i <= n; ++i) Nodes[i] = new Node(read(), i);

    // 读取每个节点的父节点编号，并链接节点
    for (long long i = 2; i <= n; ++i) LinkNode(Nodes[read()], Nodes[i]);

    long long Index = 0;

    // 处理每个测试类别
    for (long long i = 1; i <= m; ++i) {
        RemovedPairs = 0;
        Index = read();  // 读取测试的目标类别
        Node* CurRoot = Nodes[1];  // 从根节点开始

        // 继续提问直到只剩下一个子类别
        while (CurRoot->Child) {
            long long SumWeight = AccWeights(CurRoot);  // 计算当前子树的权重和
            long long CurMin = SumWeight, CurIdx = 0;  // 初始化当前最小差值和索引
            Bianli(CurRoot, SumWeight, CurMin, CurIdx);  // 遍历子树，选择最佳提问节点

            cout << CurIdx << ' ';  // 输出当前最佳提问节点

            // 根据用户的回答（是否包含目标节点）调整树结构
            if (HasTarIndex(Nodes[CurIdx], Index)) {
                CurRoot = Nodes[CurIdx];  // 如果目标节点在当前子树中，则进入子树继续提问
            } else {
                // 否则移除该节点并保存移除的父子关系
                RemovedParents[RemovedPairs] = Nodes[CurIdx]->Above->Index;
                RemovedChilds[RemovedPairs] = Nodes[CurIdx]->Index;
                ++RemovedPairs;
                RemoveNode(Nodes[CurIdx]);
            }
        }
        ReBuild();  // 恢复被移除的节点
        cout << '\n';
    }

    // 释放节点内存
    for (long long i = 1; i <= n; ++i) delete Nodes[i];

    return 0;
}

5. 时间与空间复杂度分析

时间复杂度：

树的构建与权重计算：构建树的复杂度为 O(n)，每个节点的权重计算需要遍历所有子节点，因此递归计算权重的时间复杂度为 O(n)。
提问策略执行：在每次提问时，我们需要遍历整个树结构，时间复杂度为 O(n)。总的复杂度为 O(n * m)，其中 m 是测试的类别数。

空间复杂度：

空间需求：主要是存储节点和临时变量的空间，空间复杂度为 O(n)。

6. 总结与启发

在这篇文章中，我们通过分解问题、设计数据结构、实现算法，成功解决了名词分类问题。这一过程为我们提供了几个重要的启发：

复杂树结构的管理：通过灵活使用指针与结构体，我们可以有效地管理复杂的树结构，适应多变的查询需求。
递归与动态调整：递归计算和动态调整树结构的方式，使得我们能够在面对多变的输入条件时，保持准确性和灵活性。
最优选择策略：通过遍历与计算权重差值，我们能够在复杂的决策树中找到最优的提问策略，最大限度地减少提问次数。

这些方法和思想不仅适用于本题目，还可以推广到其他涉及复杂数据结构和决策的场景中。希望这篇文章能够为大家提供有价值的参考与帮助！

【CSP-J】树上搜索(问题拆解+方案构建+思考过程)