洛谷CF1006E Military Problem怎么做

Question

代码好像没问题，但全都WA了，帮我看看吧

```c++
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int maxn=2e5+2;
int n,a[maxn],q,t,u,k;  // n为节点数，a数组存储DFS序，q为查询次数，t为DFS时间戳
 
// 树节点结构，包含子节点列表和DFS访问的左右边界
struct node {
    vector<int>e;  // 存储子节点的列表
    int l,r;       // 节点在DFS序列中的左右边界
} v[maxn];
 
// 深度优先遍历，生成树的DFS序（欧拉序）
// x: 当前遍历的节点
void dfs(int x) {
    a[++t]=x;      // 记录DFS访问顺序到数组a中
    v[x].l=t;      // 记录节点x的左边界（首次访问时间）
    sort(v[x].e.begin(),v[x].e.end());  // 对子节点排序，保证按编号升序访问
    for(auto i:v[x].e) dfs(i);          // 递归访问所有子节点
    v[x].r=t;      // 记录节点x的右边界（最后访问时间）
}
 
int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);  // 加速输入输出
    cin>>n>>q;  // 输入节点数和查询次数
    
    // 构建树结构（邻接表）
    for(int i=2,x; i<=n; i++) {
        cin>>x;  // 输入节点i的父节点
        v[x].e.push_back(i);  // 将节点i添加到父节点x的子节点列表中
    }
    
    dfs(1);  // 从根节点1开始DFS遍历，生成DFS序
    
    // 处理查询
    while(q--){
        cin>>u>>k;  // 查询节点u的第k个直属子节点
        
        // 计算在DFS序中对应的位置
        int pos=v[u].l+k-1;
        
        // 判断位置是否在节点u的DFS区间内
        if(pos<=v[u].r) cout<<a[pos]<<endl;  // 若在区间内，输出对应节点
        else cout<<-1<<endl;                 // 否则输出-1表示不存在
    }
    return 0;
}

```

Answer 1

晚上好🌙🌙🌙
本答案参考通义千问

你的代码逻辑上基本正确，但存在一个关键的错误点：DFS序中节点的子节点顺序可能与你期望的不一致，导致在查询时无法正确找到第k个子节点。这个问题源于sort(v[x].e.begin(),v[x].e.end());这一行。

---

问题分析

1. DFS序的生成方式

你使用的是标准的DFS遍历，将每个节点的子节点按照编号升序排序后进行访问，这确实可以保证子节点的顺序是按编号从小到大排列的。

但是，DFS序中的子节点并不一定连续，因为 DFS 会递归地遍历所有子树，所以子节点之间的位置可能被其他子树的节点“打乱”。

例如：

• 根节点1有两个子节点2和3。
• 如果2有一个子节点4，那么DFS序可能是：1 → 2 → 4 → 3。
• 那么对于查询 u=1, k=2，答案应该是3，而不是直接取a[v[1].l +1]。

---

为什么WA？

你当前的逻辑是：

int pos = v[u].l + k - 1;
if (pos <= v[u].r) cout << a[pos];
else cout << -1;

这假设了所有子节点都在u的l到r之间，并且是连续的，但实际上DFS序中子节点之间可能夹杂着子树的节点，因此不能简单地通过加法来获取第k个子节点。

---

正确思路

要得到第k个直属子节点，必须记录每个节点的子节点列表，并按顺序访问它们。

---

解决方案

✅ 正确做法：

1. 在构建树时，保留每个节点的子节点列表（按编号排序）。
2. 在查询时，直接从该子节点列表中取出第k个元素（如果存在的话）。

---

✅ 修改后的代码如下：

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
const int maxn = 2e5 + 2;

int n, q, t;
vector<int> children[maxn]; // 每个节点的子节点列表（已按编号排序）

// 构建树结构（邻接表）
void build_tree() {
    for (int i = 2; i <= n; ++i) {
        int x;
        cin >> x;
        children[x].push_back(i); // 将i作为x的子节点
    }
    for (int i = 1; i <= n; ++i) {
        sort(children[i].begin(), children[i].end()); // 按编号升序排序
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> q;

    build_tree();

    while (q--) {
        int u, k;
        cin >> u >> k;
        if (k <= children[u].size()) {
            cout << children[u][k - 1] << endl; // 第k个子节点
        } else {
            cout << -1 << endl;
        }
    }

    return 0;
}

---

📌 重点说明

• 原题的关键点在于“直属子节点”，不是DFS序中的第k个节点。
• DFS序是欧拉序，包含所有子树的节点，不能直接用于查找直属子节点。
• 正确的做法是直接保存每个节点的子节点列表，并在查询时直接访问。

---

✅ 总结

| 问题 | 原因 | 解决方案 | |------|------|----------| | WA | 错误地认为DFS序中的位置对应于子节点的顺序 | 直接保存子节点列表并按编号排序 | | 逻辑错误 | 未考虑DFS序中子节点可能被其他子树打断 | 使用children数组存储每个节点的子节点 |

---

如果你还有其他疑问，欢迎继续提问！