本文共 1452 字，大约阅读时间需要 4 分钟。

构造符合条件的权值序列方法解析

定义Ci为i点子树中权值比i小的结点个数，给定每个节点的Ci值，我们需要构造出符合条件的权值序列。本文将详细介绍相关方法和实现思路。

方法概述

构造权值序列的关键在于确定每个节点的权值与其子树排名之间的关系。通过对节点进行深度优先搜索（DFS），我们可以构建每个节点的子树排名序列。将这些排名依据Ci值进行插入，最终得到符合条件的权值序列。

核心实现思路

代码实现

#include 
   
    
#include 
    
     
using namespace std;
const int maxn = 2e4 + 1;
int n, a, root, num[maxn], ans[maxn];
vector
     
      
       > v(maxn + 1);
void dfs(int x) {
    vector
       
         temp;
    for (int to : v[x]) {
        temp = dfs(to);
        for (int val : temp) {
            rank.push_back(val);
        }
    }
    if (num[x] > rank.size()) {
        printf("NO");
        exit(0);
    }
    rank.insert(rank.begin() + num[x], x);
    return rank;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d %d", &a, &num[i]);
        if (a == 0) {
            root = i;
        } else {
            v[a].push_back(i);
        }
    }
    vector
        
          range = dfs(root); // 以下为权值序列生成逻辑 }
        
       
      
     
    
   

代码解释

这种方法确保了每个节点的权值与其子树排名关系准确无误，符合Ci的定义。通过DFS递归实现，保证了代码的高效性和正确性。