在运维中心收集到的一批样本中，每条样本包含 m 个二值特征与一个二分类标签（0=正常，1=劣化）。请基于 ID3 决策树训练一个二叉分类器，并对 q 条查询样本给出预测结果。 规则与细节 · 划分准则：信息增益（Entropy + Information Gain）。在当前节点，从“尚未使用”的特征中选择信息增益最大的进行二分。 · 并列处理：若多个特征增益相同，选择“特征下标更小”的那个。 · 终止与叶子： · 若当前样本标签全同，直接返回该标签； · 若没有任何特征能带来正的增益（或特征已经用尽），返回“多数标签”；若平票，返回 0。 · 为保证可预测性，某次划分若一侧样本为空，该子结点直接作为“多数标签叶子”（平票仍为 0）。 · 预测：从根出发，按节点记录的特征下标读取 0/1 向左/向右，直到叶子。
第一行：n m 接下来 n 行：每行 m+1 个整数，前 m 个为特征值（0/1），最后 1 个为标签（0/1） 下一行：q 接下来 q 行：每行 m 个整数，表示待预测样本的特征（0/1）
共 q 行，每行 1 个整数（0 或 1），为对应查询样本的预测值
6 2 0 0 0 0 1 0 1 0 1 1 1 1 0 0 0 1 1 1 3 0 1 1 0 1 1
0 1 1
考点：二分
限制 1 秒 / 256MB ｜ 标准输入输出
参考方向：二分
把「求最优值」转化为「判定某值是否可行」，用单调性二分逼近答案。
思路框架（二分 通法 · 非本题专属）
实现要点：模板：while (lo < hi) { mid = (lo+hi)/2; if (check(mid)) hi = mid; else lo = mid+1; } 求最小可行值。
复杂度：时间 O(check 的代价 × log(答案范围)) ｜ 空间 O(1)
该范式的通法易错点
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。
样例 1：输入 6 2 / 0 0 0 / 0 1 0 / 1 0 1 / 1 1 1 / 0 0 0 / 1 1 1 / 3 / 0 1 / 1 0 / 1 1 → 输出 0 / 1 / 1
在根节点，按信息增益选择特征1（与特征2并列时，因下标更小而被选中）；左支（特征1=0）标签几乎全为 0，右支（特征1=1）标签几乎全为 1；因此三个查询分别预测为 0、1、1。
解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。
本题来源：2025年秋招-华为-9月24号AI岗。