CSP2019树上的数 贪心链表并查集

发表于 更新于 分类于 阅读次数：

树上的数 首先，枚举数字，再枚举目的地，贪心。先考虑一下菊花图怎么做： 对于菊花图把边的选择顺序写出来，发现可以串成一条链。对于一次移动，可以发现限制是两条边必须一前一后的移动。那么用一些数据结构维护这个东西就可以了。 考虑一般情况，对于一次$x \rightarrow y$的移动，有这样的限制：$x$出边是$x$最先走的，$y$入边是$y$最后走的，中间点的两条边是连续的。 注意到限制对于点是独立的。那么每个点都可以看做一个菊花，有第一条，最后一条，以及一些先后的顺序的限制。 对于每个菊花，一条路径是好的，除了不能成环，起点终点的边这样的限制外，还需要满足：当起点和终点在一条链的时候，这条链必须把所有点串起来。 菊花内部在过程中会产生很多链，用链表维护。当然也可以用并查集。 求解是$O(n^3)$的，但是按DFS序枚举目的地，就可以做到总复杂度$O(n^2)$了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <bits/stdc++.h>

const int N = 2050;

int n, id[N];

struct Graph {
  int to, nxt;
} G[N * 2];
int head[N], tot;

struct Chain {
  int fir, lst, cnt;
  bool st[N], ed[N];
  int fa[N];
  inline void init() {
    fir = lst = cnt = 0;
    for (int i = 1; i <= n; ++i) {
      fa[i] = i;
      st[i] = ed[i] = 1;
    }
  }
  int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
  }
} t[N];

inline void addedge(int x, int y) {
  G[++tot] = { y, head[x] };
  head[x] = tot, ++t[x].cnt;
}

int find(int x, int fa) {
  int ans = n + 1;
  if (fa && (!t[x].lst  t[x].lst == fa) && !(t[x].fir && t[x].cnt > 1 && t[x].find(fa) == t[x].find(t[x].fir)) && t[x].ed[fa])
    ans = x;
  for (int i = head[x]; i; i = G[i].nxt) {
    if ((i >> 1) != fa) {
      int y = G[i].to;
      if (!fa) {
        if ((!t[x].fir  t[x].fir == (i >> 1)) && t[x].st[i >> 1]
            && !(t[x].lst && t[x].cnt > 1 && t[x].find(i >> 1) == t[x].find(t[x].lst)))
          ans = std::min(ans, find(y, i >> 1));
      } else {
        if ((!t[x].lst  fa != t[x].lst) && (!t[x].fir  (i >> 1) != t[x].fir) && t[x].find(fa) != t[x].find(i >> 1)
            && t[x].st[i >> 1] && t[x].ed[fa] && !(t[x].fir && t[x].lst && t[x].cnt > 2
            && t[x].find(fa) == t[x].find(t[x].fir) && t[x].find(i >> 1) == t[x].find(t[x].lst)))
          ans = std::min(ans, find(y, i >> 1));
      }
    }
  }
  return ans;
}

int merge(int x, int fa, int to) {
  if (x == to) {
    t[x].lst = fa;
    return 1;
  }
  for (int i = head[x]; i; i = G[i].nxt) {
    if ((i >> 1) != fa) {
      int y = G[i].to;
      if (merge(y, i >> 1, to)) {
        if (!fa) {
          t[x].fir = i >> 1;
        } else {
          t[x].ed[fa] = t[x].st[i >> 1] = 0;
          --t[x].cnt;
          t[x].fa[t[x].find(fa)] = t[x].find(i >> 1);
        }
        return 1;
      }
    }
  }
  return 0;
}

inline void solve() {
  std::cin >> n; tot = 1;
  for (int i = 1; i <= n; ++i) {
    head[i] = 0;
    t[i].init();
    std::cin >> id[i];
  }
  for (int i = 1, x, y; i < n; ++i) {
    std::cin >> x >> y;
    addedge(x, y);
    addedge(y, x);
  }
  if (n == 1) { std::cout << "1\n"; return; }
  for (int i = 1; i <= n; ++i) {
    int to = find(id[i], 0);
    merge(id[i], 0, to);
    std::cout << to << ' ';
  }
  std::cout << '\n';
}

int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);
  int T; std::cin >> T;
  while (T--) solve();
  return 0;
}