树分裂

// 没有过全部测试用例（怀疑是用例问题）  仅通过46.67%
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct TreeNode {
  int id, weight;
  struct TreeNode *left, *right;
} TreeNode, *PTreeNode;

typedef struct {
  struct TreeNode* t1; // <
  struct TreeNode* t2; // >=
} Result;

PTreeNode buildTree(int (*data)[3], int index) {
  if (!index) return NULL;
  PTreeNode root = (PTreeNode) malloc(sizeof(TreeNode));
  if (!root) return NULL;
  
  root->id     = index;
  root->weight = *(*(data + index) + 2);
  root->left   = buildTree(data, **(data + index));
  root->right  = buildTree(data, *(*(data + index) + 1));
  return root;
}

Result split(PTreeNode root, int target) {
  if (!root)
    return (Result) { .t1 = NULL, .t2 = NULL };
  
  Result res;
  if (root->weight >= target) {
    res = split(root->left, target);
    root->left = res.t2;
    res.t2 = root;
  } else {
    res = split(root->right, target);
    root->right = res.t1;
    res.t1 = root;
  }
  return res;
}

void output(PTreeNode node) {
  printf("{%d %d}, ", (*node).id, (*node).weight);
}

void create_mapping(PTreeNode root, PTreeNode* repos) {
  if (!root) return;
  *(repos + root->id) = root;
  create_mapping(root->left, repos);
  create_mapping(root->right, repos);
}

// debug helper function
void preorder(PTreeNode root, void (*visit) (PTreeNode)) {
  if (!root) return;
  visit(root);
  preorder(root->left, visit);
  preorder(root->right, visit);
}

int main(void) {
  int n, v;
  scanf("%d %d", &n, &v);
  int data[n + 1][3], has_parent[n + 1];
  memset(has_parent, 0x0000, sizeof has_parent);
  
  int i, l, r, w;
  for (i = 1; i <= n; ++i) {
    scanf("%d %d %d", &l, &r, &w);
    data[i][0] = l;
    data[i][1] = r;
    data[i][2] = w;
    if (l != 0) has_parent[l] = 1;
    if (r != 0) has_parent[r] = 1;
  }
  
  int root_idx = 1; 
  while (has_parent[root_idx]) ++root_idx;
  
  PTreeNode root = buildTree(data, root_idx);
  
  PTreeNode repos[n + 1];
  create_mapping(root, repos);
 
  split(root, v);
  
  PTreeNode node;
  for (i = 1; i <= n; ++i) {
    node = *(repos + i);
    l = node->left ? node->left->id : 0;
    r = node->right ? node->right->id : 0;
    printf("%d %d\n", l, r);
  }
  
  return 0;
}

# 思路：仅通过46.67%
# 将小于给定值的节点的权值和索引放在一个列表内，同理将不小于给定值的节点放在另一个列表内
# 将两个列表按权值排序
# 两棵树全部只有左子树，即最小权值的做叶节点，然后按权值升序给节点找到其父节点
lineone = input().split()
n, v = int(lineone[0]), int(lineone[1])
nodes = []
res = []
for i in range(n):
    linen = input().split()
    nodes.append([int(linen[0]), int(linen[1]), int(linen[2])])
    res.append([])
 
greater = []
smaller = []
for ind in range(1,len(nodes)+1):
    if nodes[ind-1][-1] < v:
        smaller.append([nodes[ind-1][-1], ind])
    else:
        greater.append([nodes[ind-1][-1], ind])
greater = sorted(greater, key=lambda x: x[0])
smaller = sorted(smaller, key=lambda x: x[0])
 
temp = 0
for i in range(len(greater)):
    ind = greater[i][1]-1
    if i == 0:
        res[ind].append(0)
        res[ind].append(0)
        temp = ind + 1
    else:
        res[ind].append(temp)
        res[ind].append(0)
        temp = ind + 1
 
temp = 0
for i in range(len(smaller)):
    ind = smaller[i][1]-1
    if i == 0:
        res[ind].append(0)
        res[ind].append(0)
        temp = ind + 1
    else:
        res[ind].append(temp)
        res[ind].append(0)
        temp = ind + 1
 
for i in range(len(res)):
    print(str(res[i][0]) + " " + str(res[i][1]))