【CSP-S2019】D1T3 树上的数_综合

CSP2019 D1T3 树上的数

题目

题目描述

给定一个大小为 $n$ 的树，它共有 $n$ 个结点与 $n ? 1$ 条边，结点从 $\sim n$ 编号。初始时每个结点上都有一个 $\sim n$ 的数字，且每个 $\sim n$ 的数字都只在恰好一个结点上出现。

接下来你需要进行恰好 $n ? 1$ 次删边操作，每次操作你需要选一条未被删去的边，此时这条边所连接的两个结点上的数字将会交换，然后这条边将被删去。

$n ? 1$ 次操作过后，所有的边都将被删去。此时，按数字从小到大的顺序，将数字 $\sim n$ 所在的结点编号依次排列，就得到一个结点编号的排列 $P_i$ ?。现在请你求出，在最优操作方案下能得到的字典序最小的 $P_i$ ?。

分析

我们不难有一个贪心的想法：枚举每个数，将它们分别移动到尽可能小的节点上面去。

考虑把一个数字送到另一个数字上，对于一个点我们一共有三种限制：

对于起始点，选中的边必须先于其他所有边删掉；
对于中转点，选中的两条边必须顺序删掉；
对于结束点，选中的边必须在最后删掉。

那么这样一来我们将删的边的顺序排成一排，可以发现我们可以用双向链表来维护。于是我们给每个节点 $u$ 都建立一个双向链表。

但在计算答案的过程中，一定有一些是连不到一起的，这种情况我们直接把它们看成一堆链表就可以了。

于是就可以用两次 DFS 解决这个问题：

枚举每个数字，第一次 DFS 找出它能够到达的最小的节点，第二次 DFS 更新链表。

总时间复杂度 $O(N^2)$ 。

各种情况的讨论还是看代码吧。。。太复杂了 ~~我不想写~~ 写不出来。。。

参考代码

简直是分类大讨论啊。。。

#include <cstdio>
#include <algorithm>
using namespace std;const int Maxn = 2000;struct Edge {
    int to;Edge *nxt;
};
Edge pool[Maxn * 2 + 5];
Edge *G[Maxn + 5], *ecnt;
inline void addedge(int u, int v) {
    Edge *p = ++ecnt;p->to = v, p->nxt = G[u];G[u] = p;
}int N, num[Maxn + 5];int pre[Maxn + 5][Maxn + 5], nxt[Maxn + 5][Maxn + 5];//链表的前后指针
int head[Maxn + 5][Maxn + 5], tail[Maxn + 5][Maxn + 5];//链表的头节点和尾节点
int len[Maxn + 5][Maxn + 5];//链表的大小int deg[Maxn + 5];inline void clear() {
    ecnt = &pool[0];for(int i = 1; i <= N; i++)G[i] = NULL;for(int i = 1; i <= N + 1; i++)for(int j = 1; j <= N + 1; j++)len[i][j] = pre[i][j] = nxt[i][j] = head[i][j] = tail[i][j] = 0;for(int i = 1; i <= N; i++)deg[i] = 0;
}int minp;
void DFS1(int u, int fa) {
    //找到对应的最小的节点int st = head[u][fa], ed = tail[u][fa];if(fa == N + 1) {
    //这是起点for(Edge *p = G[u]; p != NULL; p = p->nxt) {
    //枚举这个点上的第一条应该删掉的边int v = p->to;int t1 = head[u][v], t2 = tail[u][v];if(t1 != v || (pre[u][fa] == t2 && len[u][t1] < deg[u]))continue;//若这个点 v 已经有了一个起点且并不是它自己//或者，这个点的链表形成了一个环但总长度无法将所有的边连接在一起//那么这条边就不能够被第一个选中DFS1(v, u);}} else {
    if(fa == ed) {
    //如果 u 后面并没有选到一条边，那么枚举一个点if(pre[u][N + 1] == 0 && (nxt[u][N + 1] != st|| len[u][st] == deg[u])) minp = min(minp, u);//当 u 能被当做结束点的时候//首先，这个点的最后一条没有删的边没有指定//其次，如果这个点的链表的开头会连上结尾，那么长度必须等于 u 的出度//否则长度随意for(Edge *p = G[u]; p != NULL; p = p->nxt) {
    int v = p->to;int t1 = head[u][v], t2 = tail[u][v];if(st == t1 || t1 != v || nxt[u][N + 1] == v)continue;//若这两条边 (u, fa) 和 (u, v) 已经在同一个链表上面//或者，这条边不是一条开始边，即它之前还有其他的边要被删掉//或者这条边就是一条开始边//那么 (u, v) 就不能够接在 (u, fa) 后面if(nxt[u][N + 1] == st && pre[u][N + 1] == t2&& len[u][st] + len[u][t1] < deg[u]) continue;//若边 (u, v) 和边 (u, fa) 为应该最先删和最后删的边的尾部和头部//那么它们的长度加起来必须等于这个点的度数//否则就是提前成了一个环，是不合法的状态DFS1(v, u);}} else DFS1(nxt[u][fa], u);//否则只能够按照我们之前已经确定了的路径找}
}
inline void merge(int u, int st, int ed) {
    int t1 = head[u][st], t2 = tail[u][ed];nxt[u][st] = ed, pre[u][ed] = st;for(int i = t1; i != 0 && i != N + 1; i = nxt[u][i])head[u][i] = t1, tail[u][i] = t2;len[u][t1] += len[u][ed];
}//将两个链表连在一起
bool DFS2(int u, int fa) {
    //更新链表
//当这个函数返回 true 时则表示找到了路径if(u == minp) {
    //找到了这个数的结束点pre[u][N + 1] = fa, nxt[u][fa] = N + 1;//将它设为最后一条边，并设为最后删掉的边//注意：我们用 N + 1 来标识最后一条边return true;}int st = head[u][fa], ed = tail[u][fa];if(fa == N + 1) {
    for(Edge *p = G[u]; p != NULL; p = p->nxt) {
    int v = p->to;int t1 = head[u][v], t2 = tail[u][v];if(t1 != v || (pre[u][N + 1] == t2 && len[u][t1] < deg[u]))continue;//参照 DFS1 中对应位置上的注释if(DFS2(v, u)) {
    //找出正确的路径了nxt[u][N + 1] = v, pre[u][v] = N + 1;//将 u 标记为起始点并加入链表return true;}}} else {
    //中转点if(fa == ed) {
    //如果 u 后面并没有选到一条边，那么枚举一个点for(Edge *p = G[u]; p != NULL; p = p->nxt) {
    int v = p->to;int t1 = head[u][v], t2 = tail[u][v];if(st == t1 || t1 != v || nxt[u][N + 1] == v)continue;if(nxt[u][N + 1] == st && pre[u][N + 1] == t2&& len[u][st] + len[u][t1] < deg[u]) continue;//参考 DFS1 中的对应位置注释if(DFS2(v, u)) {
    merge(u, fa, v);//这时我们应该将两个链表连到一起了return true;}}} else DFS2(nxt[u][fa], u);//按照既定路径找下去}return false;
}int main() {
    
#ifdef LOACLfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifint _;scanf("%d", &_);while(_--) {
    scanf("%d", &N);clear();for(int i = 1; i <= N; i++)scanf("%d", &num[i]);for(int i = 1; i < N; i++) {
    int u, v;scanf("%d %d", &u, &v);addedge(u, v), addedge(v, u);++deg[u], ++deg[v];pre[u][v] = pre[v][u] = nxt[u][v] = nxt[v][u] = 0;head[u][v] = tail[u][v] = v, head[v][u] = tail[v][u] = u;len[u][v] = len[v][u] = 1;}if(N == 1) {
    puts("1");continue;}for(int i = 1; i <= N; i++) {
    minp = N + 1;DFS1(num[i], N + 1);DFS2(num[i], N + 1);printf("%d%c", minp, (i == N) ? '\n' : ' ');}}return 0;
}