题解 P5659 【树上的数【民间数据】】

dsidsi · 2019-11-22 23:29:46 · 题解

Description

给定一棵树和每个节点上的初始数字，删除一条边的效果是交换被这条边连接的两个节点上的数字交换。

设p_i表示数字i在哪个节点，要求合理安排删除n-1条边的顺序，使得排列p字典序最小，

n \leq 2000

Solution

考虑把一个数字从一个节点运送到另一个节点的过程。

可以发现，限制总共有3种：

对于起点，选择的边要求是这个点所有边中第一条删除的；
对于中间的点，要求选择的两条边的删除顺序必须连续；
对于终点，选择的边要求是这个点所有边中最后一条删除的。

那么考虑对于每个点建立一张图，图上面的点代表这个点连出去的一条边。

在这张图上的一条有向边代表出点要在入点之后马上选择，同时记录这个点钦定的第一条边和最后一条边。每个点的图不相关。

那么考虑贪心，从小到大确定每个数字的最终位置，同时保证不矛盾。

矛盾的情况有三种：

图的形式不是若干条链的形式；
第一个点（边）有入边，最后一个点（边）有出边；
第一个点（边）所在的链的链尾是最后一个点（边），但是还有其他的点不在链中。

从每个数字的起始点出发，保证从根到这个点的路径不会引起矛盾，更新答案即可。

我写的是并查集，如果想写O(n^2)的链表写法，那么只要满足每次相连的是两条链的链首和链尾，然后分别记录链首、链尾的所在的链的链尾和链首即可。

#include <bits/stdc++.h>
using namespace std;

inline int gi()
{
    char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    int sum = 0;
    while ('0' <= c && c <= '9') sum = sum * 10 + c - 48, c = getchar();
    return sum;
}

const int maxn = 2005;

inline void chkmin(int &a, int b) {if (a > b) a = b;}

int n, nump[maxn];

struct edge
{
    int to, next;
} e[maxn * 2];
int h[maxn], tot;

struct node
{
    int fst, lst, cnt, fa[maxn];
    bool bg[maxn], ed[maxn];

    void clear() {fst = lst = cnt = 0; for (int i = 1; i <= n; ++i) fa[i] = i, bg[i] = ed[i] = 1;}
    int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
} t[maxn];

inline void add(int u, int v)
{
    e[++tot] = (edge) {v, h[u]}; h[u] = tot; ++t[u].cnt;
    e[++tot] = (edge) {u, h[v]}; h[v] = tot; ++t[v].cnt;
}

int dfs1(int u, int fe)
{
    int res = n + 1;
    if (fe && (!t[u].lst || t[u].lst == fe)) {
        if (t[u].ed[fe] && !(t[u].fst && t[u].cnt > 1 && t[u].find(fe) == t[u].find(t[u].fst))) 
            res = u;
    }
    for (int i = h[u], v, te; v = e[i].to, i; i = e[i].next) {
        if (fe == (te = (i >> 1))) continue;
        te = i >> 1;
        if (!fe) {
            if (!t[u].fst || t[u].fst == te) {
                if (!t[u].bg[te]) continue;
                if (t[u].lst && t[u].cnt > 1 && t[u].find(te) == t[u].find(t[u].lst)) continue;
                chkmin(res, dfs1(v, te));
            } else continue;
        } else {
            if (fe == t[u].lst || te == t[u].fst || t[u].find(fe) == t[u].find(te)) continue;
            if (!t[u].ed[fe] || !t[u].bg[te]) continue; 
            if (t[u].fst && t[u].lst && t[u].cnt > 2 && t[u].find(fe) == t[u].find(t[u].fst) && t[u].find(te) == t[u].find(t[u].lst)) continue;

            chkmin(res, dfs1(v, te));
        }
    }
    return res;
}

int dfs2(int u, int fe, int p)
{
    if (u == p) return t[u].lst = fe, 1;
    for (int i = h[u], v, te; v = e[i].to, i; i = e[i].next)
        if (fe != (te = (i >> 1))) 
            if (dfs2(v, te, p)) {
                if (!fe) t[u].fst = te;
                else {
                    t[u].ed[fe] = t[u].bg[te] = 0; --t[u].cnt;
                    t[u].fa[t[u].find(fe)] = t[u].find(te);
                }
                return 1;
            }
    return 0;
}

int main()
{
    int T = gi();
    while (T--) {
        tot = 1;
        memset(h + 1, 0, sizeof(int) * n);

        n = gi();
        for (int i = 1; i <= n; ++i) t[i].clear();
        for (int i = 1; i <= n; ++i) nump[i] = gi();
        for (int i = 1; i < n; ++i) add(gi(), gi());

        if (n == 1) {puts("1"); continue;}

        for (int p, i = 1; i <= n; ++i) {
            p = dfs1(nump[i], 0);
            dfs2(nump[i], 0, p);
            printf("%d ", p);
        }
        puts("");
    }

    return 0;
}