public class TreeNode { //树节点的结构 int val; TreeNode left; TreeNode right; public TreeNode(int val) { this.val = val; left = null; right = null; } public static void main(String[] args) { Scanner in = new Scanner(System.in); int T = in.nextInt(); for (int i = 0; i < T; i++) { int N = in.nextInt(); //先把每个节点存在数组tree中 TreeNode[] tree = new TreeNode[N]; int[] val = new int[N]; int[] left = new int[N]; int[] right = new int[N]; int[] root = new int[N]; for (int j = 0; j < N; j++) { val[j] = in.nextInt(); tree[j] = new TreeNode(val[j]); left[j] = in.nextInt(); right[j] = in.nextInt(); } //添加节点的左右子节点，同时记录哪些点是有父节点的，有父节点的把root数组的相应位置标记为1 for (int j = 0; j < N; j++) { if (left[j] != -1) { tree[j].left = tree[left[j]]; root[left[j]] = 1; } if (right[j] != -1) { tree[j].right = tree[right[j]]; root[right[j]] = 1; } } //广度优先搜索 Queue<TreeNode> q = new LinkedList<TreeNode>(); //根节点一定不是任何节点的左右子节点，所以root数组中为0的那个节点就是根结点 for (int j = 0; j < N; j++) { if (root[j] == 0) { q.add(tree[j]); break; } } //presum记录上一层的和，sum记录下一层的和 int presum = -1; boolean flag = true; while (!q.isEmpty()) { int size = q.size();//size记录当前层有多少个节点 int index = 0;//index记录当前层有多少个节点已经搜索过了 int sum = 0;//记录当前层节点的权值之和 while (index < size) { TreeNode tmp = q.poll(); sum += tmp.val; index++; if (tmp.left != null) q.add(tmp.left); if (tmp.right != null) q.add(tmp.right); } if (presum == -1) { presum = sum;//第一层时presum为-1，令他等于当前层的结果 } else if (presum > sum) {//不为第一层时比较当前层和上一层的和是否满足递增，不满足则退出循环输出NO flag = false; break; } } if (flag) System.out.println("YES"); else System.out.println("NO"); } } }