华为校招&实习机试在线OJ刷题系统 ｜ 在线OJ注册使用教程
目录
题目
思路
Code
题目
题目内容：
CART（Classification and Regression Trees）分类树通过二元切分递归地将数据划分为不纯度最小的子集。它通过基尼系数（Gini Index）计算最优分裂特征和点，形成二叉树结构，适用于处理离散和连续数据。本题要求应用CART分类树模型预测客户是否购房。给定一个训练数据集，通过构建CART二叉决策树，使用基尼指数选择最优特征和最优切分点，对输入的测试样本进行预测。
划分规则：对于每个特征，尝试所有可能的取值作为切分点，将数据划分为左子集和右子集：左子集为特征值 = 切分点的样本；右子集为特征值 ≠ 切分点的样本。
数据集说明：包含4个特征和1个标签，所有取值的输入转换为整数枚举。特征1：年龄段（0: 18-30岁; 1: 31-40岁; 2: 41-55岁; 3: 56岁及以上）；特征2：婚姻状况（0: 单身; 1: 恋爱; 2: 已婚）；特征3：是否有房（0: 无; 1: 有）；特征4：是否有工作（0: 无; 1: 有）；标签：购房结果（0: 否; 1: 是）。
基尼指数计算公式：对于包含 K 个类别的数据集，$p_k$ 为指定标签的样本占比：$Gini(D) = 1 - \sum_{k=1}^{K} p_k^2$。
加权基尼指数：对于特征 A 的切分点 v，将 D 划分为 $D_1(A = v)$ 和 $D_2(A \neq v)$：$Gini(D, A, v) = \frac{|D_1|}{|D|} \times Gini(D_1) + \frac{|D_2|}{|D|} \times Gini(D_2)$。
预测规则：叶子节点的预测类别为该节点中样本数最多的类别；若多个类别样本数相同，取类别编号较小的。
停止分裂条件（满足任一条件即停止）：节点中所有样本标签相同；节点中样本数小于 2；无法找到使基尼指数降低的切分点。
平局处理规则：遍历特征时，按特征编号从小到大（特征1 → 特征2 → 特征3 → 特征4）；对于每个特征，遍历其所有可能的取值作为切分点，按取值从小到大；计算每个切分点的加权基尼指数，选择基尼指数最小的切分点；当多个特征的基尼指数相同且均为最小值时，选择特征编号较小的特征；当同一特征内多个取值的基尼指数相同且均为最小值时，选择取值较小的作为切分点（即左子集为 等于该较小值）。
输入格式：第一行给出整数 N，表示训练集的客户人数（4 ≤ N ≤ 20）；随后 N 行，每行 5 个整数，依次是 4 个特征和 1 个标签，整数之间以空格分隔；接下来一行给出整数 M，表示待预测的样本人数（1 ≤ M ≤ 10）；随后 M 行，每行 4 个整数，依次是 4 个特征。
输出格式：输出一行，共 M 个整数，依次为 M 个测试样本在所建 CART 树上的预测结果，整数之间以空格分隔。
样例1
输入：
20 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 0 1 1 1 1 0 2 0 1 1 1 0 0 0 0 1 0 1 1 1 1 1 0 1 1 1 1 1 0 0 1 2 1 0 0 2 0 0 1 1 2 0 1 0 1 2 1 0 0 0 2 1 1 1 1 2 2 0 0 0 3 0 0 0 0 3 0 1 1 0 3 1 0 1 1 3 1 1 0 0 3 2 0 1 0 10 1 1 1 0 2 0 0 1 3 2 0 1 0 0 1 0 1 2 1 0 2 1 0 0 3 0 1 1 0 1 1 1 1 0 0 0 2 2 0 0输出：
0 1 0 0 0 0 0 1 0 0思路
整体思路：按题面规则现建一棵 CART 二叉分类树。每个节点选一个特征和一个取值做二元切分，左子树放该特征等于这个取值的样本，右子树放不等于的样本。只有加权基尼指数比当前节点严格更小的切分才接受，否则停止分裂变成叶子。
1. 读入 N 条训练记录（4 个特征 + 1 个标签）和 M 条测试记录。
2. 建树是递归过程。先统计当前节点样本里标签 0 和标签 1 的人数：样本数小于 2、标签已纯（只剩一类）、或找不到能严格降低基尼的切分，三种情况任一成立就直接做叶子；叶子预测人数更多的类别，两类人数打平取编号较小的 0。
3. 每个节点枚举切分：特征按编号 1 到 4 从小到大，每个特征在节点内出现过的取值也按从小到大。把当前节点的基尼写成整数分数 (tot^2 - c0^2 - c1^2) / tot^2，左右子集同理，加权基尼通分后是 num/den = (g1*n2 + g2*n1) / (tot*n1*n2)。全程用整数交叉相乘比较大小，避免浮点误差。
4. 接受条件是加权基尼严格小于当前节点基尼（num*base_d < base_n*den 才接受）；而更新最优切分时用的是严格小于（num*best_den < best_num*den 才替换），相等不替换。这样平局自然留下更小的特征编号和更小的取值，正好满足题面的平局规则。
5. 一侧为空的切分（所有样本该特征都等于或不等于某取值）直接跳过，没有意义。
6. 预测时每个测试样本从根往下走：特征值等于切分值进左子树，否则进右子树，走到叶子输出类别。
复杂度：特征 4 个、每个特征取值不超过 4 种，都是常数。每个节点只扫自己的样本，每个样本出现在从根到叶的一条链上，建树 O(N^2)；M 个测试样本各走一条根到叶路径，预测 O(N*M)。N ≤ 20、M ≤ 10，规模极小。关键坑点：一是叶子平局（两类人数相同）取编号小的 0；二是"严格降低基尼才分裂"和"平局保留更小特征/取值"这两条都要用严格不等号实现，写成 <= 会破坏平局规则；三是切分点的左子集是"等于该取值"的样本，不要建反。
Code
C++
#include <bits/stdc++.h> using namespace std; int a[25][5]; // 数样本集合里标签 0 和标签 1 各有多少个 pair<int, int> stat(const vector<int>& ids) { int c0 = 0; for (int i : ids) if (a[i][4] == 0) c0++; return {c0, (int)ids.size() - c0}; } // 递归建树。叶子用 {-1, 类别} 表示；内部节点 {特征, 切分值, 左, 右} struct Node { int f, v; int left = -1, right = -1; // 子节点下标，-1 表示叶子 int lab; // 叶子的预测类别 }; vector<Node> tree; int build(const vector<int>& ids) { pair<int, int> cc = stat(ids); int c0 = cc.first, c1 = cc.second; int tot = ids.size(); // 叶子预测：人数多的类别；打平取编号小的 0 int lab = c0 >= c1 ? 0 : 1; // 样本不足 2 个，或标签已纯，停止分裂 if (tot < 2 || c0 == 0 || c1 == 0) { tree.push_back({-1, 0, -1, -1, lab}); return tree.size() - 1; } // 当前节点的基尼写成整数分数：(tot^2 - c0^2 - c1^2) / tot^2 long long baseN = (long long)tot * tot - (long long)c0 * c0 - (long long)c1 * c1; long long baseD = (long long)tot * tot; bool found = false; long long bestNum = 0, bestDen = 1; int bestF = -1, bestV = 0; vector<int> bestL, bestR; // 平局规则：特征编号从小到大，同一特征内取值从小到大； // 基尼用整数交叉相乘比较，只有严格变小才替换，平局留下更小的特征/取值 for (int f = 0; f < 4; f++) { set<int> vals; for (int i : ids) vals.insert(a[i][f]); for (int v : vals) { vector<int> L, R; for (int i : ids) (a[i][f] == v ? L : R).push_back(i); if (L.empty() || R.empty()) continue; // 一侧为空没意义 pair<int, int> lc = stat(L); pair<int, int> rc = stat(R); int l0 = lc.first, l1 = lc.second; int r0 = rc.first, r1 = rc.second; long long n1 = L.size(), n2 = R.size(); // 左右子集的基尼分子：n^2 - c0^2 - c1^2 long long g1 = n1 * n1 - (long long)l0 * l0 - (long long)l1 * l1; long long g2 = n2 * n2 - (long long)r0 * r0 - (long long)r1 * r1; // 加权基尼通分：num/den long long num = g1 * n2 + g2 * n1; long long den = (long long)tot * n1 * n2; // 只有严格降低基尼的切分才接受 if (num * baseD >= baseN * den) continue; if (!found || num * bestDen < bestNum * den) { found = true; bestNum = num; bestDen = den; bestF = f; bestV = v; bestL = L; bestR = R; } } } if (!found) { tree.push_back({-1, 0, -1, -1, lab}); // 找不到能降低基尼的切分，变成叶子 return tree.size() - 1; } int me = tree.size(); tree.push_back({bestF, bestV, -1, -1, lab}); int lc = build(bestL); // 注意先占位再递归，避免递归时 vector 扩容失效 int rc = build(bestR); tree[me].left = lc; tree[me].right = rc; return me; } int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) for (int j = 0; j < 5; j++) scanf("%d", &a[i][j]); vector<int> ids(n); for (int i = 0; i < n; i++) ids[i] = i; int root = build(ids); int m; scanf("%d", &m); for (int k = 0; k < m; k++) { int x[4]; for (int j = 0; j < 4; j++) scanf("%d", &x[j]); // 沿树往下走：特征值等于切分值进左子树，否则进右子树 int cur = root; while (tree[cur].f >= 0) cur = x[tree[cur].f] == tree[cur].v ? tree[cur].left : tree[cur].right; printf("%d%c", tree[cur].lab, k + 1 < m ? ' ' : '\n'); } return 0; }Java
import java.util.*; import java.io.*; public class Solution { static int[][] a; // 数样本集合里标签 0 和标签 1 各有多少个 static int[] stat(List<Integer> ids) { int c0 = 0; for (int i : ids) if (a[i][4] == 0) c0++; return new int[]{c0, ids.size() - c0}; } // 递归建树。返回节点编号；节点 = [特征, 切分值, 左孩子, 右孩子, 叶子类别] // 叶子的特征存 -1，预测类别存 leafLab static int[][] tree = new int[200][5]; static int nodeCnt = 0; static int build(List<Integer> ids) { int[] c = stat(ids); int c0 = c[0], c1 = c[1]; int tot = ids.size(); // 叶子预测：人数多的类别；打平取编号小的 0 int lab = c0 >= c1 ? 0 : 1; // 样本不足 2 个，或标签已纯，停止分裂 if (tot < 2 || c0 == 0 || c1 == 0) { tree[nodeCnt] = new int[]{-1, 0, -1, -1, lab}; return nodeCnt++; } // 当前节点的基尼写成整数分数：(tot^2 - c0^2 - c1^2) / tot^2 long baseN = (long) tot * tot - (long) c0 * c0 - (long) c1 * c1; long baseD = (long) tot * tot; boolean found = false; long bestNum = 0, bestDen = 1; int bestF = -1, bestV = 0; List<Integer> bestL = null, bestR = null; // 平局规则：特征编号从小到大，同一特征内取值从小到大； // 基尼用整数交叉相乘比较，只有严格变小才替换，平局留下更小的特征/取值 for (int f = 0; f < 4; f++) { TreeSet<Integer> vals = new TreeSet<>(); for (int i : ids) vals.add(a[i][f]); for (int v : vals) { List<Integer> L = new ArrayList<>(), R = new ArrayList<>(); for (int i : ids) { if (a[i][f] == v) L.add(i); else R.add(i); } if (L.isEmpty() || R.isEmpty()) continue; // 一侧为空没意义 int[] lc = stat(L), rc = stat(R); long n1 = L.size(), n2 = R.size(); // 左右子集的基尼分子：n^2 - c0^2 - c1^2 long g1 = n1 * n1 - (long) lc[0] * lc[0] - (long) lc[1] * lc[1]; long g2 = n2 * n2 - (long) rc[0] * rc[0] - (long) rc[1] * rc[1]; // 加权基尼通分：num/den long num = g1 * n2 + g2 * n1; long den = (long) tot * n1 * n2; // 只有严格降低基尼的切分才接受 if (num * baseD >= baseN * den) continue; if (!found || num * bestDen < bestNum * den) { found = true; bestNum = num; bestDen = den; bestF = f; bestV = v; bestL = L; bestR = R; } } } if (!found) { tree[nodeCnt] = new int[]{-1, 0, -1, -1, lab}; // 无法降低基尼，变成叶子 return nodeCnt++; } int me = nodeCnt++; tree[me] = new int[]{bestF, bestV, -1, -1, lab}; int leftChild = build(bestL); // 先递归再回填孩子编号 int rightChild = build(bestR); tree[me][2] = leftChild; tree[me][3] = rightChild; return me; } public static void main(String[] args) throws IOException { // 全程只用 nextInt 读整数，避免 Scanner 在不同读取模式间切换造成错位 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StreamTokenizer tk = new StreamTokenizer(br); tk.nextToken(); int n = (int) tk.nval; a = new int[n][5]; for (int i = 0; i < n; i++) for (int j = 0; j < 5; j++) { tk.nextToken(); a[i][j] = (int) tk.nval; } List<Integer> ids = new ArrayList<>(); for (int i = 0; i < n; i++) ids.add(i); int root = build(ids); StringBuilder sb = new StringBuilder(); tk.nextToken(); int m = (int) tk.nval; for (int k = 0; k < m; k++) { int[] x = new int[4]; for (int j = 0; j < 4; j++) { tk.nextToken(); x[j] = (int) tk.nval; } // 沿树往下走：特征值等于切分值进左子树，否则进右子树 int cur = root; while (tree[cur][0] >= 0) cur = x[tree[cur][0]] == tree[cur][1] ? tree[cur][2] : tree[cur][3]; if (k > 0) sb.append(' '); sb.append(tree[cur][4]); } System.out.println(sb); } }Go
package main import ( "bufio" "fmt" "os" "sort" ) var a [25][5]int // node 递归树的节点。叶子：f = -1，lab 是预测类别；内部节点：特征 f、切分值 v、左右孩子 type node struct { f, v, left, right, lab int } var tree []node // stat 数样本集合里标签 0 和标签 1 各有多少个 func stat(ids []int) (int, int) { c0 := 0 for _, i := range ids { if a[i][4] == 0 { c0++ } } return c0, len(ids) - c0 } func build(ids []int) int { c0, c1 := stat(ids) tot := len(ids) // 叶子预测：人数多的类别；打平取编号小的 0 lab := 1 if c0 >= c1 { lab = 0 } // 样本不足 2 个，或标签已纯，停止分裂 if tot < 2 || c0 == 0 || c1 == 0 { tree = append(tree, node{-1, 0, -1, -1, lab}) return len(tree) - 1 } // 当前节点的基尼写成整数分数：(tot^2 - c0^2 - c1^2) / tot^2 baseN := int64(tot)*int64(tot) - int64(c0)*int64(c0) - int64(c1)*int64(c1) baseD := int64(tot) * int64(tot) found := false var bestNum, bestDen int64 bestF, bestV := -1, 0 var bestL, bestR []int // 平局规则：特征编号从小到大，同一特征内取值从小到大； // 基尼用整数交叉相乘比较，只有严格变小才替换，平局留下更小的特征/取值 for f := 0; f < 4; f++ { valSet := map[int]bool{} for _, i := range ids { valSet[a[i][f]] = true } vals := make([]int, 0, len(valSet)) for v := range valSet { vals = append(vals, v) } sort.Ints(vals) for _, v := range vals { var L, R []int for _, i := range ids { if a[i][f] == v { L = append(L, i) } else { R = append(R, i) } } if len(L) == 0 || len(R) == 0 { continue // 一侧为空没意义 } l0, l1 := stat(L) r0, r1 := stat(R) n1, n2 := int64(len(L)), int64(len(R)) // 左右子集的基尼分子：n^2 - c0^2 - c1^2 g1 := n1*n1 - int64(l0)*int64(l0) - int64(l1)*int64(l1) g2 := n2*n2 - int64(r0)*int64(r0) - int64(r1)*int64(r1) // 加权基尼通分：num/den num := g1*n2 + g2*n1 den := int64(tot) * n1 * n2 // 只有严格降低基尼的切分才接受 if num*baseD >= baseN*den { continue } if !found || num*bestDen < bestNum*den { found = true bestNum, bestDen = num, den bestF, bestV = f, v bestL, bestR = L, R } } } if !found { tree = append(tree, node{-1, 0, -1, -1, lab}) // 无法降低基尼，变成叶子 return len(tree) - 1 } me := len(tree) tree = append(tree, node{bestF, bestV, -1, -1, lab}) lc := build(bestL) // 先递归再回填孩子编号 rc := build(bestR) tree[me].left = lc tree[me].right = rc return me } func main() { // 输入很小，但按惯例把缓冲区放大，防止大输入被截断 sc := bufio.NewScanner(os.Stdin) sc.Buffer(make([]byte, 1024*1024), 1024*1024) sc.Split(bufio.ScanWords) next := func() int { sc.Scan() v := 0 for _, c := range sc.Bytes() { v = v*10 + int(c-'0') } return v } w := bufio.NewWriter(os.Stdout) defer w.Flush() n := next() for i := 0; i < n; i++ { for j := 0; j < 5; j++ { a[i][j] = next() } } ids := make([]int, n) for i := range ids { ids[i] = i } root := build(ids) m := next() for k := 0; k < m; k++ { x := [4]int{} for j := 0; j < 4; j++ { x[j] = next() } // 沿树往下走：特征值等于切分值进左子树，否则进右子树 cur := root for tree[cur].f >= 0 { if x[tree[cur].f] == tree[cur].v { cur = tree[cur].left } else { cur = tree[cur].right } } if k > 0 { fmt.Fprint(w, " ") } fmt.Fprint(w, tree[cur].lab) } fmt.Fprint(w, "\n") }C
#include <stdio.h> #include <stdlib.h> #define MAXN 25 #define MAXNODE 60 int a[MAXN][5]; /* 数样本集合里标签 0 和标签 1 各有多少个 */ void stat(int *ids, int cnt, int *c0, int *c1) { *c0 = 0; for (int i = 0; i < cnt; i++) if (a[ids[i]][4] == 0) (*c0)++; *c1 = cnt - *c0; } /* 递归建树。叶子：f = -1，lab 是预测类别；内部节点：特征 f、切分值 v、左右孩子 */ typedef struct { int f, v, left, right, lab; } Node; Node tree[MAXNODE]; int nodeCnt = 0; int build(int *ids, int cnt) { int c0, c1; stat(ids, cnt, &c0, &c1); int tot = cnt; /* 叶子预测：人数多的类别；打平取编号小的 0 */ int lab = c0 >= c1 ? 0 : 1; /* 样本不足 2 个，或标签已纯，停止分裂 */ if (tot < 2 || c0 == 0 || c1 == 0) { tree[nodeCnt] = (Node){-1, 0, -1, -1, lab}; return nodeCnt++; } /* 当前节点的基尼写成整数分数：(tot^2 - c0^2 - c1^2) / tot^2 */ long long baseN = (long long)tot * tot - (long long)c0 * c0 - (long long)c1 * c1; long long baseD = (long long)tot * tot; int found = 0, bestF = -1, bestV = 0; long long bestNum = 0, bestDen = 1; int bestL[MAXN], bestR[MAXN], bestLn = 0, bestRn = 0; int L[MAXN], R[MAXN]; /* 平局规则：特征编号从小到大，同一特征内取值从小到大； 基尼用整数交叉相乘比较，只有严格变小才替换，平局留下更小的特征/取值 */ for (int f = 0; f < 4; f++) { /* 收集该特征在节点内出现过的取值并排序（取值最多 4 种） */ int vals[4], vn = 0; for (int i = 0; i < cnt; i++) { int v = a[ids[i]][f], seen = 0; for (int j = 0; j < vn; j++) if (vals[j] == v) seen = 1; if (!seen) vals[vn++] = v; } for (int i = 0; i < vn; i++) /* 小规模插入排序 */ for (int j = i + 1; j < vn; j++) if (vals[j] < vals[i]) { int t = vals[i]; vals[i] = vals[j]; vals[j] = t; } for (int vi = 0; vi < vn; vi++) { int v = vals[vi], ln = 0, rn = 0; for (int i = 0; i < cnt; i++) { if (a[ids[i]][f] == v) L[ln++] = ids[i]; else R[rn++] = ids[i]; } if (ln == 0 || rn == 0) continue; /* 一侧为空没意义 */ int l0, l1, r0, r1; stat(L, ln, &l0, &l1); stat(R, rn, &r0, &r1); long long n1 = ln, n2 = rn; /* 左右子集的基尼分子：n^2 - c0^2 - c1^2 */ long long g1 = n1 * n1 - (long long)l0 * l0 - (long long)l1 * l1; long long g2 = n2 * n2 - (long long)r0 * r0 - (long long)r1 * r1; /* 加权基尼通分：num/den */ long long num = g1 * n2 + g2 * n1; long long den = (long long)tot * n1 * n2; /* 只有严格降低基尼的切分才接受 */ if (num * baseD >= baseN * den) continue; if (!found || num * bestDen < bestNum * den) { found = 1; bestNum = num; bestDen = den; bestF = f; bestV = v; for (int i = 0; i < ln; i++) bestL[i] = L[i]; for (int i = 0; i < rn; i++) bestR[i] = R[i]; bestLn = ln; bestRn = rn; } } } if (!found) { tree[nodeCnt] = (Node){-1, 0, -1, -1, lab}; /* 找不到能降低基尼的切分，变成叶子 */ return nodeCnt++; } int me = nodeCnt++; tree[me] = (Node){bestF, bestV, -1, -1, lab}; tree[me].left = build(bestL, bestLn); tree[me].right = build(bestR, bestRn); return me; } int main(void) { int n; if (scanf("%d", &n) != 1) return 0; for (int i = 0; i < n; i++) for (int j = 0; j < 5; j++) scanf("%d", &a[i][j]); int ids[MAXN]; for (int i = 0; i < n; i++) ids[i] = i; int root = build(ids, n); int m; scanf("%d", &m); for (int k = 0; k < m; k++) { int x[4]; for (int j = 0; j < 4; j++) scanf("%d", &x[j]); /* 沿树往下走：特征值等于切分值进左子树，否则进右子树 */ int cur = root; while (tree[cur].f >= 0) cur = x[tree[cur].f] == tree[cur].v ? tree[cur].left : tree[cur].right; printf("%d%c", tree[cur].lab, k + 1 < m ? ' ' : '\n'); } return 0; }Python
import sys def main(): data = sys.stdin.read().split() pos = 0 def nxt(): nonlocal pos v = int(data[pos]) pos += 1 return v n = nxt() a = [[nxt() for _ in range(5)] for _ in range(n)] def stat(ids): # 数一下样本集合里标签 0 和标签 1 各有多少个 c0 = sum(1 for i in ids if a[i][4] == 0) return c0, len(ids) - c0 def build(ids): c0, c1 = stat(ids) tot = len(ids) # 叶子预测：人数多的类别；打平取编号小的 0 lab = 0 if c0 >= c1 else 1 # 样本不足 2 个，或标签已纯，停止分裂 if tot < 2 or c0 == 0 or c1 == 0: return [-1, lab] # 当前节点的基尼写成整数分数： (tot^2 - c0^2 - c1^2) / tot^2 base_n = tot * tot - c0 * c0 - c1 * c1 base_d = tot * tot best = None # 平局规则：特征编号从小到大，同一特征内取值从小到大； # 基尼用分数比较，只有严格变小才更新，平局自然留下更小的特征/取值 for f in range(4): for v in sorted({a[i][f] for i in ids}): left = [i for i in ids if a[i][f] == v] right = [i for i in ids if a[i][f] != v] if not left or not right: continue # 一侧为空的切分没有意义 l0, l1 = stat(left) r0, r1 = stat(right) n1, n2 = len(left), len(right) # 左右子集的基尼也写成整数分子： n^2 - c0^2 - c1^2 g1 = n1 * n1 - l0 * l0 - l1 * l1 g2 = n2 * n2 - r0 * r0 - r1 * r1 # 加权基尼 = (g1/n1 + g2/n2) / tot，通分后是 num/den num = g1 * n2 + g2 * n1 den = tot * n1 * n2 # 只有严格降低基尼的切分才接受（num*base_d < base_n*den） if num * base_d >= base_n * den: continue if best is None or num * best[1] < best[0] * den: best = [num, den, f, v, left, right] if best is None: return [-1, lab] # 找不到能降低基尼的切分，变成叶子 return [best[2], best[3], build(best[4]), build(best[5])] def ask(node, x): # 沿树往下走：特征值等于切分值进左子树，否则进右子树 while node[0] >= 0: node = node[2] if x[node[0]] == node[1] else node[3] return node[1] root = build(list(range(n))) m = nxt() ans = [str(ask(root, [nxt() for _ in range(4)])) for _ in range(m)] print(" ".join(ans)) main()