树上的排列 题解

题目分析

这道题要求通过一系列边删除操作（每次删除前交换两端节点的数字），使得最终数字1到n所在节点编号排列的字典序最小。

关键点：

• 树结构，每个节点初始有一个1~n的数字
• 删除边时交换两端节点的数字
• 需要找到最优的删边顺序，使最终排列字典序最小

解题思路

核心观察

1. 操作可逆性：交换操作可以看作数字在树上移动
2. 字典序最小：要让数字1在尽可能靠前的节点，数字2在尽可能靠前的节点（在数字1位置确定的情况下），依此类推
3. 连通性维护：使用链表结构维护每个节点的邻接关系

算法设计

代码采用了贪心 + DFS + 链表维护的方法：

主要步骤：

1. 初始化邻接表：为每个节点维护邻接边的链表
2. 贪心选择：每次选择当前能到达的最小节点编号
3. DFS搜索：从当前数字位置出发，找到能到达的最小节点
4. 链表更新：删除已使用的边，更新连通关系

代码详解

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
using namespace std;

const int N = 2005;
int n, x[N], y[N], p[N], ans[N], xx[N], yy[N], Min;
vector<int> G[N], H[N], pre[N], nxt[N];
int lst_p[N], lst_e[N], nxt_e[N], num[N];

// 添加边
void add_edge(int x, int y, int id) {
    G[x].push_back(y);
    H[x].push_back(id);
}

void init() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &p[i]);  // 数字i初始所在的节点
        G[i].clear(); H[i].clear();
        pre[i].clear(); nxt[i].clear();
        // 初始化各种数组
        x[i] = y[i] = xx[i] = yy[i] = ans[i] = lst_p[i] = nxt_e[i] = lst_e[i] = 0;
    }
    
    for (int i = 1; i < n; ++i) {
        scanf("%d%d", &x[i], &y[i]);
        add_edge(x[i], y[i], i);
        add_edge(y[i], x[i], i);
        xx[i] = G[x[i]].size();  // 边在x[i]邻接表中的位置
        yy[i] = G[y[i]].size();  // 边在y[i]邻接表中的位置
    }
}

// DFS查找从当前节点能到达的最小节点
void dfs(int now, int id_e) {
    if (nxt[now][id_e] != id_e) return;
    
    // 检查是否可以到达当前节点
    if (pre[now].back() == G[now].size() + 1 && 
        !(num[now] != 2 && !pre[now][id_e])) {
        Min = min(Min, now);
    }
    
    // 遍历邻接边
    for (int i = 0; i < G[now].size(); ++i) {
        if (nxt[now][i + 1] == id_e || pre[now][i + 1] != i + 1) 
            continue;
            
        if (num[now] != 2 && !pre[now][id_e] && 
            nxt[now][i + 1] == pre[now].size() - 1)
            continue;
            
        int to = G[now][i];
        int idx = H[now][i];
        nxt_e[to] = i + 1;
        lst_p[to] = now;
        
        // 确定边在目标节点的位置
        if (x[idx] == to) {
            lst_e[to] = xx[idx];
            dfs(to, xx[idx]);
        } else {
            lst_e[to] = yy[idx];
            dfs(to, yy[idx]);
        }
    }
}

// 在链表中连接两个位置，相当于删除中间的边
void link(int o, int a, int b) {
    nxt[o][a] = nxt[o][b];
    pre[o][b] = pre[o][a];
    nxt[o][pre[o][a]] = nxt[o][b];
    pre[o][nxt[o][b]] = pre[o][a];
    --num[o];
}

void solve() {
    // 初始化每个节点的链表
    for (int i = 1; i <= n; ++i) {
        pre[i].resize(G[i].size() + 2);
        for (int j = 0; j < pre[i].size(); ++j)
            pre[i][j] = j;
        nxt[i] = pre[i];  // 复制
        num[i] = pre[i].size();
    }
    
    // 对每个数字进行处理
    for (int i = 1; i <= n; ++i) {
        Min = n + 1;
        dfs(p[i], 0);  // 从数字i的初始位置出发
        ans[i] = Min;   // 数字i最终能到达的最小节点
        
        // 更新链表，删除使用的路径
        link(Min, lst_e[Min], pre[Min].size() - 1);
        
        int tmp = Min;
        // 沿着路径向上更新
        while (lst_p[tmp] != p[i]) {
            link(lst_p[tmp], lst_e[lst_p[tmp]], nxt_e[tmp]);
            tmp = lst_p[tmp];
        }
        
        link(p[i], 0, nxt_e[tmp]);
    }
    
    // 输出结果
    for (int i = 1; i <= n; ++i)
        printf("%d%c", ans[i], " \n"[i == n]);
}

int main() {
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);
    int t;
    scanf("%d", &t);
    while (t--) {
        init();
        solve();
    }
    return 0;
}

算法原理详解

1. 问题转化

将问题转化为：对于每个数字i，找到从它的初始位置p[i]出发，通过剩余的边能到达的最小节点编号。

2. 链表维护连通性

为每个节点维护两个链表：

• pre[i]: 前驱链表
• nxt[i]: 后继链表

这些链表表示当前节点还能通过哪些边与其他节点连通。

3. DFS搜索过程

dfs(now, id_e) 从节点now出发，通过id_e指定的边，搜索能到达的所有节点，并记录最小的节点编号。

4. 贪心策略

对于数字1到n依次处理：

1. 找到数字i能到达的最小节点Min
2. 将数字i移动到节点Min
3. 删除使用的路径上的边（更新链表）

5. 链表操作

link(o, a, b) 操作将节点o的链表中位置a和b连接起来，相当于删除了中间的边。

复杂度分析

• 时间复杂度：O(n²)，每个数字需要O(n)的DFS
• 空间复杂度：O(n²)，存储邻接表和链表

样例解析

以第一个样例为例：

5
2 1 3 5 4  # 数字1在节点2，数字2在节点1，...
1 3
1 4  
2 4
4 5

处理过程：

• 数字1：从节点2出发，能到达的最小节点是1
• 数字2：从节点1出发，能到达的最小节点是3（因为边1-3还在）
• 数字3：从节点3出发，能到达的最小节点是4
• 等等...

最终得到排列：1 3 4 2 5

关键技巧

1. 链表维护：高效表示和更新连通关系
2. 贪心选择：按数字顺序逐个确定最优位置
3. DFS搜索：找到当前能到达的所有节点
4. 路径删除：使用后立即删除路径，避免重复使用

总结

这道题的解题亮点：

1. 问题重构：将删边操作转化为数字移动问题
2. 数据结构：使用链表高效维护动态连通性
3. 贪心算法：按字典序要求逐个确定数字位置
4. 完整性：处理了多组数据和大规模情况

算法通过巧妙的链表设计和贪心策略，在O(n²)时间内解决了这个复杂的树操作问题，展示了处理动态连通性问题的有效方法。