解题思路

1. 数据结构设计 用一个结构体（或类）存储单个节点的全部信息：

   • feature_index 分裂特征下标
   • threshold 分裂阈值
   • left 左子节点行号
   • right 右子节点行号
   • label 分类结果（仅在叶子节点有效）

题目内容

在无线通信系统中为了资源调配更加合理和及时，需要对未来一段时间网络的负载做出预判以确定资源调配的优先级。决策树是一种常用的模型，可以根据采集到的状态数据，结合时间段、天气等因素来推测合理的资源调配优先级。现在将一个训练好的分类决策树模型$Tree$ 安装在系统中，请实现决策树的推算算法，根据输入特征返回资源调配优先级。

输入描述

输入包含多行数据：

• 首行是属性参数；
• 后续$(m)$行是决策树模型的结构数据；
• 再后续$(n)$行是待推理的样本。

$1$. 属性参数（首行）

包含 $3$个$int$类数据，分别表示：

• 特征数量 $(f)$，
• 树模型的节点数 $(m)$，
• 待推理样本的行数$(n)$。

$2$. 决策树模型 $(T)$ $((T)$ 是 $(m)$ 行$5$ 列的矩阵$)$

• 一行数据表示决策树的一个节点，首行表示根节点(即$(T)$矩阵中的第$0$ 行)，共有$(m)$个节点。
• $5$个列分别表示：
  1. 分裂特征的下标
  2. 分裂特征的阈值
  3. 当前节点左子节点的行号（即 $(T)$矩阵中第几行）
  4. 当前节点右子树的行号
  5. 分类结果（即资源调配优先级）

数据类型分别为：$int, float, int, int, int$；下标和行号均从$0$开始。

• 模型结构中有意义的数据均$(\geq 0)$，无意义数据统一用$(-1)$表示。 例如：叶子节点无分裂特征，因此该字段填入$(-1)$。
• 决策规则：若样本特征的取值$(\leq)$ 分裂特征的阈值，则进入左子树，否则进入右子树。

$3.$ 待推理样本($(n)$ 行 $(f)$ 列)

• 一行数据表示一个待推理的样本；
• 每行包含$(f)$个特征，数据类型为 $float$。

输出描述

返回分类结果。 注：一行一个分类结果，数据类型为 $int$。

样例1

输入

2 5 2
0 2.5 1 2 -1
-1 -1 -1 -1 1
1 5.0 3 4 -1
-1 -1 -1 -1 2
-1 -1 -1 -1 3
1.2 3.4
5.6 6.0

输出

1
3

说明

• 第 $1$ 行：特征数量为$2$，模型节点数为$5$，待推理样本为 $2$ 条。
• 第$2$ 到 $6$ 行：决策树模型，共 $5$ 个节点。首行（第$2$行输入数据）为根节点。
• 第 $7$ 到$8$ 行：$2$ 个待推理样本，每个样本包含$2$ 个特征。

输出：两条样本的推理结果分别为 分类 1、分类 3。

样例2

输入

3 9 2
0 6.1 1 2 -1
2 7.0 3 4 -1
1 6.5 5 6 -1
-1 -1 -1 -1 1
1 10.3 7 8 -1
-1 -1 -1 -1 5
-1 -1 -1 -1 6
-1 -1 -1 -1 3
-1 -1 -1 -1 4
3.2 9.2 6.2
6.3 3.2 12.0

输出

1
5

说明

第 $1$ 行：特征数量为$3$，模型节点数为 $9$，待推理样本为 $2$条。

第$2$ 到$10$ 行：决策树模型，共$9$ 个节点。首行（第 $2$ 行输入数据）为根节点。

第$11$ 到$12$行：$2$ 个待推理样本，每个样本包含 $3$ 个特征。

输出：两条样本的推理结果分别为 分类 1、分类 5。