题目内容

某电商平台利用机器学习进行交易反欺诈。算法团队已经离线训练好了一个随机森林模型，现在需要你来实现该模型在线上的预测引擎。

随机森林由多棵独立的决策树（Decision Tree）组成。每笔交易包含 $M$ 个特征属性。预测时，每棵决策树都会从根节点开始独立对交易进行评估：

• 如果遇到内部节点，会判断交易的第 $idx$ 个特征值是否小于等于阈值 $val$：如果是，则走向左子节点；否则走向右子节点。
• 如果走到叶子节点，该树会输出一个预测类别：$0$ 代表正常交易，$1$ 代表欺诈交易。

最终，整个森林的预测结果采用“多数表决”（Majority Voting）原则，即统计所有树输出的类别，得票数最多的类别作为最终结果。注意：如果 $0$ 和 $1$ 的票数相同，出于用户体验考虑，一律判定为正常交易（输出 $0$）。

请你编写程序，根据给定的随机森林结构和 $N$ 笔交易数据，输出每笔交易的最终预测结果。

解答要求

时间限制：C/C++ 1000ms，其他语言：2000ms

内存限制：C/C++ 512MB，其他语言：1024MB

输入描述

• 第一行：3个用空格分隔的整数 $T$，$M$，$N$。$T$ 为树的数量，$M$ 为特征维度数，$N$ 为待预测的交易笔数。
• 接下来是 $T$ 棵树的结构定义。对于每棵树：
  • 第一行：一个整数 $K$，表示该树共有 $K$ 个节点。节点编号为 $1$ 到 $K$。根节点编号固定为 $1$。
  • 接下来 $K$ 行，按节点编号 $1$～$K$ 的顺序依次描述每个节点。每行以一个整数 $type$ 开头：
    • 若 $type=1$，代表内部节点，后接4个整数 $idx$ $val$ $left$ $right$。 表示如果特征序列中第 $idx$ 个特征值 $\le val$，则跳至编号为 $left$ 的节点，否则跳至编号为 $right$ 的节点。（特别提示：特征索引 $idx$ 从 $1$ 开始，即取值范围为 $1$～$M$）
    • 若 $type=0$，代表叶子节点，后接1个整数 $label$（值为 $0$ 或 $1$），表示该节点的分类结果。
• 最后是 $N$ 行交易数据：每行包含 $M$ 个用空格分隔的整数，代表一笔交易的 $M$ 个特征值。

输出描述

• 输出共 $N$ 行，每行一个整数（$0$ 或 $1$），代表模型对该笔交易的最终预测结果。

样例1

输入：

2 1 1
1
0 1
1
0 0
5

输出：

0

解释：两棵树的预测结果分别为 $1$ 和 $0$，票数 $1:1$ 相同。根据规则：如果票数相同，一律判定为正常交易（输出 $0$），故输出 $0$。不能输出 $1$。

样例2

输入：

3 2 2
3
1 1 10 2 3
0 0
0 1
3
1 2 5 2 3
0 1
0 0
1
0 1
8 8
12 2

输出：

0
1

解释：共有3棵树，2个特征，2笔交易。

对于第一笔交易 $[8,8]$：

• 第1棵树：根节点判断特征1（值为8）$\le 10$ 成立，走向左节点（编号2），节点2是叶子，输出0。
• 第2棵树：根节点判断特征2（值为8）$\le 5$ 不成立，走向右节点（编号3），节点3是叶子，输出0。
• 第3棵树：根节点即为叶子，直接输出1。表决结果：两个0，一个1，最终输出0。对于第二笔交易 $[12,2]$：同理遍历得出的输出为：第1棵树输出1，第2棵树输出1，第3棵树输出1，最终输出1。

提示

输入/输出约束（边界范围）

• $1 \le T \le 51$
• $1 \le M \le 50$
• $1 \le N \le 2000$
• $1 \le K \le 500$
• $1 \le idx \le M$，且节点编号 $left,right \in [1,K]$ 符合值和阈值 $val$ 取值范围均在 $[-10^5,10^5]$ 之间。题目保证给定的树形结构合法，不存在环，且每个内部节点一定存在两个有效的子节点。