pts:195
T1: 95
T2:100
T3: 0
T1
[CSP-S2019] 格雷码
数论，递归
solution
找规律，不难发现每位之间格雷码都有一定的关系，例如： 4 位格雷码的每一个数把相比于 3 位格雷码加上的部分再去掉，剩下的都能在 (3) 位格雷码中找到，那么输出某一个格雷码时，可以不停的向更低位寻找它所在的位置，如果在前一半就输出 1，否则输出 0
T2
[CSP-S2019] 括号树
树形结构，树的应用
solution
状态：
-
(f[i]) 表示根节点到 (i) 号点合法括号的方案数
-
(last[i]) 根节点到 (i) 号点距离 (i) 最近还没有匹配的左括号的位置
-
(tot[i]) 表示 (i) 号点到根节点连续匹配的括号个数
注意：
((())) 没有连续匹配的括号，所以 (tot[6] = 1)
而 ()()() 连续匹配了 3 个括号，所以 (tot[6] = 3)
(tot) 的统计是为了方便更新 (f) 数组。例如: ()()( 如果再添加一个 ) ,那么这个新组成的括号可以与前面的 () 和 ()() 形成新的合法括号序列
转移
若 (s[u] = '(')，(last[u] = u)，(f[u]) 和 (tot[u]) 直接继承父亲
若 (s[u] = ')') ，并且 (last[u]) 存在（否则无法匹配）
(last[u] = last[fa[last[u]]])
(tot[u] = tot[fa[last[u]]] + 1)
(f[u] = f[fa[u]] + tot[u])
code
/*
work by:Ariel_
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#define int long long
using namespace std;
const int N = 5e5 + 5;
int n, fa[N], f[N], last[N], tot[N], ans, cnt;
char s[N];
signed main(){
n = read();
scanf("%s", s + 1);
for (int i = 2; i <= n; i++) cin >> fa[i];
for (int i = 1; i <= n; i++){
f[i] = f[fa[i]], last[i] = last[fa[i]];
if (s[i] == '(') last[i] = i;
else if(s[i] == ')' && last[i]) {
tot[i] = tot[fa[last[i]]] + 1;
last[i] = last[fa[last[i]]];
f[i] += tot[i];
}
ans ^= i * f[i];
}
printf("%lld
", ans);
return 0;
}
T3
[CSP-S2019]树上的数
树形结构
solution（from: Cryin）
发现题解有点错误，所以还是再写一遍
subtask1 N (leq) 10
(O(N!)) 暴力枚举所有的删边顺序，取字典数最小的一组
subtask2 存在度数为 N - 1 的节点
显然该图一定是个菊花图
设菊花图入度为 (N-1) 的点为 (rt)
每次删边一段必定是 (rt) ，假设删边顺序是 (p)，(p_i) 表示第 (i) 次删的点编号。
第 (i) 次删的边就是 (rt -> p_i)
有个性质：每次删边，当前 (p_i) 的点权就确定了 (交换之后就不能 (p_i) ) 就不能换了
发现 (a_{p_1}) 到了(p_2)，(a_{p_2}) 到了(p_3) ，(a_{p_{n-1}}) 到了(rt)
显然这是一个环
(rt->p_1->p_2->p_3...->p_{n-1}->rt)
要想让字典序最小，我们贪心的选择能得到的最小的数字，并且这个环要不能是多个小环
如果想让数字 (i) 到 (j) 点的话，那么首先 (j) 这个点没有用过，并且 (j) 和 (p_i) 不在同一个环里(防止提前成环，用并查集维护)
时间复杂度 (O(N^2))
subtask3 树是一条链 (Nleq) 160
按照菊花图的思路，考虑数字 (i) 走向 (j) 点（考试的时候推出来了，但不会写qwq）
规定三个点
- 起点：数字 (i) 所在位置
- 途经点：从起点到终点路过的那些点
- 终点：(j) 点所在的位置
我们先把链 (dfs) 处理一下，记录链上第 (i) 个点是 (a_i) ，(u) 点是第 (num_u)个。
我们考虑着三种点有什么特殊的性质
首先对于一个点，删边顺序有两种，先删掉左后删右或者先删右后删左。
用一个 (tag) 数组表示一下这个点删边顺序 (tag = 0) 表示这个点没有标记，(tag = 1)表示先删掉左后删右，(tag = 2) 表示先删右后删左
假如 (num_{p_i} leq num_j) 及 (p_i) 在 (j) 的左边，所以 (i) 要向右走
起点
先删右后删左，很显然吧，如果如果先删了左边 (i) 点就跑到左边去啦，并且也不回来了
途径点
先删左后删右，先删掉左边是为了把 (i) 点从左边接过来，然后再把 (i) 点从右边送过去
终点
先删右后删左，先删掉右边是为了保证 (i) 点到了终点之后不再跑出去，删左边是为了从左边把 (i) 点结果来
(num_{p_i} > num_j) 反过来就好了
我们可以对应的打一个 (tag) 上去。 如果想让 (i) 走向点 (j) 那么就要与先前的 ( ext{tag}) 不矛盾
时间复杂度为 (O(N^3))
subtask4 树是一条链 (N leq 2000)
对于数字 (i) 可以 ( ext{dfs}) 遍历整条链找到最小的合法的位置。然后再标记一下。
枚举每一个数字时间复杂度 (O(N))
找点和标记的复杂度 $ O(N)$
总复杂度 (O(N^2))
subtask5 树形态任意 (N leq 2000)
和链 $ O(N^2)$ 算法一样考虑对于一个点，连接它的边，删边必然有顺序，而且每个点的删边顺序互不影响，这样，对于每个点的删边顺序我们维护成一个集合，这个顺序集构成一条链的形式
我们用并查集维护每个点的删边顺序集，当前点的最先删除的边的序号，最后删除点的边的序号，当前点有多少条边未删除。
(fir_u) 为这个点删边集的最先删除的边。
(lst_u) 为这个点删边集的最后删除的边。
(pre_p) 表示这条边的前驱。
(nxt_p) 表示这条边后继。
同样考虑将数字 (i) 点移到 (j) 点，考虑 起点， 途径点， 终点
起点
考虑起点所连的所有边的删边顺序
1.1： (i) 点指向 (j) 点的边肯定要第一个被删，否则 (i) 就偏离轨道了
1.2： 如果当前点最后删的边 (last_u) 已经确定，如果 (last_u) 和 (fir_u) 已经在同一个集合里面了，但是这个点的度数 > 1，说明有的边要么在起点之前，要么在起点之后，那么该点的删边序列就不再是一个链了，所以这种情况要排除
途经点
2.1： (i) 走到 (j) 经过的点 (u) ，并且走过 ((v,u)) 和 ((u,w)) 这两条边，并且分别标号为 (p_1) 和 (p_2)，首先这两条边的编号一定是连续的，并且一定是先删 (p_1)， 再删 (p_2)
2.2： ((v,u)) 和 ((u,w)) 两条边已经在这个点的边集合中了，(p_1) 和 (p_2) 显然不合法，因为如果加入就会成环了
2.3: (pre_{p2}) 已经确定，或者 (nxt_{p1}) 已经确定，显然不合法，因为两条边连不到一起去了
2.4： (fir_u) 和 (las_u) 已经确定，并且 (fir_u) 和 (p_1) 在同一个集合，(las_u) 和 (p_2)在同一个集合，那么就会直接连成一个环，无法再形成一个链了（除非该点只剩两条边没被删）
终点
如果它是终点，显然它不能当起点， 从 (i) 过来的那条边一定是最后删滴
3.1： 终点 (u) 最后删除的边 (lst_u) 要么为 0，要么为 (p) (从 (i) 过来的边)
3.2： 如果 (p) 边有后继边不能当做终点 ((nxt_p eq 0))
3.3： 为了避免提前成环，所以 (fir_u) 和 (p) 在同一个集合的时候，该点的入度只能为 1，也就是只有 (p) 边没有加入集合
code
/*
work by:Ariel_
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
#define int long long
using namespace std;
const int N = 2000 + 50;
const int M = 4000 + 50;
int read(){
int x = 0,f = 1; char c = getchar();
while(c < '0'||c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') {x = x*10 + c - '0'; c = getchar();}
return x*f;
}
int T, n, ind[N], head[N], E, Max_In, x[N], y[N], p[N];
struct edge {
int u, v, nxt;
} e[M];
void add_edge (int u, int v) {
e[++E] = (edge){u, v, head[u]};
head[u] = E;
}
void Clear () {
E = 1;
for (int i = 0; i <= n; i++) head[i] = ind[i] = 0;
}
namespace subtask2 {//菊花图
int fa[N], ans[N];
bool vis[N];
int find (int x) {return x == fa[x] ? x : fa[x] = find (fa[x]);}
void merge (int x, int y) {fa[find (x)] = find (y);}
void main () {
for (int i = 1; i <= n; i ++) fa[i] = i, vis[i] = 0;
for (int i = 1; i <= n; i ++)//数字
for (int j = 1; j <= n; j ++)//放置的点的编号
if (!vis[j] && (i == n || find (j) != find (p[i]))) {//确定能构成一个大的环，防止提前结成环
ans[i] = j; vis[j] = 1; merge (j, p[i]);
break;
}
for (int i = 1; i <= n; i ++) printf ("%lld%c", ans[i], i == n ? '
' : ' ');
}
}
//起点：先右后左, 途径点：先左后右, 终点：先右后左
//tag = 0 ：没有标记，tag = 1 先左后右，tag = 2 先右后左:
//namespace subtask3 {//链
// int cnt, a[N], ans[N], tag[N], num[N];//
// bool vis[N];
// void dfs (int u, int f) {//预处理一下链
// a[num[u] = ++cnt] = u;
// for (int i = head[u]; i; i = e[i].nxt) {
// int v = e[i].v;
// if (v == f) continue;
// dfs (v, u);
// }
// }
// bool check_l (int p1, int p2) { //判断p1->p2的可行性
// if (tag[p1] == 1 || tag[p2] == 1) return false;
// for (int i = p1 + 1; i < p2; i ++ ) if (tag[i] == 2) return false;
// return true;
// }
// void push_l (int p1, int p2) { //打标记
// if (p1 != 1 && p1 != n) tag[p1] = 2;
// if (p2 != 1 && p2 != n) tag[p2] = 2;
// for (int i = p1 + 1; i < p2; i ++ ) tag[i] = 1;
// }
// bool check_r (int p1, int p2) {
// if (tag[p1] == 2 || tag[p2] == 2) return false;
// for (int i = p2 + 1; i < p1; i ++ ) if (tag[i] == 1) return false;
// return true;
// }
// void push_r (int p1, int p2) {
// if (p1 != 1 && p1 != n) tag[p1] = 1;
// if (p2 != 1 && p2 != n) tag[p2] = 1;
// for (int i = p2 + 1; i < p1; i ++ ) tag[i] = 2;
// }
// void main() {
// for (int i = 1; i <= n; i ++ ) tag[i] = vis[i] = 0; cnt = 0;//预处理一下
// for (int i = 1; i <= n; i ++ ) if (ind[i] == 1) {dfs (i, 0); break;}
// for (int i = 1; i <= n; i++) {//和菊花图一个样，贪心找点替换
// for (int j = 1; j <= n; j++) {
// bool flag = false;
// if (num[p[i]] <= num[j])
// if (check_l (num[p[i]], num[j])) push_l (num[p[i]], num[j]), flag = true;
//
// else if (check_r (num[p[i]], num[j]))
// push_r (num[p[i]], num[j]), flag = true;
//
// if (flag) {ans[i] = j; vis[j] = 1;break;}
// }
// }
// for (int i = 1; i <= n; i ++ ) printf ("%lld%c", ans[i], i == n ? '
' : ' ');
// }
//}
//起点：先右后左, 途径点：先左后右, 终点：先右后左
//tag = 0 ：没有标记，tag = 1 先左后右，tag = 2 先右后左:
namespace subtask4{//链的 n^2
int cnt, a[N], ans[N], tag[N], num[N];
bool vis[N];
void dfs (int u, int f) {//预处理一下链
a[num[u] = ++cnt] = u;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].v;
if (v == f) continue;
dfs (v, u);
}
}
void push_l (int p1, int p2) { //根据每个点的规定打标记
if (p1 != 1 && p1 != n) tag[p1] = 2;
if (p2 != 1 && p2 != n) tag[p2] = 2;
for (int i = p1 + 1; i < p2; i ++) tag[i] = 1;
}
void push_r (int p1, int p2) {
if (p1 != 1 && p1 != n) tag[p1] = 1;//序列两端特判
if (p2 != 1 && p2 != n) tag[p2] = 1;
for (int i = p2 + 1; i < p1; i ++ ) tag[i] = 2;
}
int find_l (int u) {//左侧的最优点
int res = n + 1;
if (tag[num[u]] == 2) return res;
for (int j = num[u] - 1; j >= 1; j -- ) {
if (tag[j] == 1) {
if (!vis[j]) res = min (res, a[j]);
break;
}
if (tag[j] == 0 && !vis[j]) res = min (res, a[j]);
}
return res;
}
int find_r (int u) {//右侧的最优点
int res = n + 1;
if (tag[num[u]] == 1) return res;
for (int j = num[u] + 1; j <= n; j ++ ) {
if (tag[j] == 2) {
if (!vis[j]) res = min (res, a[j]);
break;
}
if (tag[j] == 0 && !vis[j]) res = min (res, a[j]);
}
return res;
}
void main() {
for (int i = 1; i <= n; i++) tag[i] = vis[i] = 0;cnt = 0;
for (int i = 1; i <= n; i++) if(ind[i] == 1) {dfs(i, 0); break;}
for (int i = 1; i <= n; i ++ ) {
int rt = find_l (p[i]), tp;
if (rt < (tp = find_r(p[i]))) push_r(num[p[i]], num[rt]);
else rt = tp, push_l(num[p[i]], num[rt]);
ans[i] = rt;
vis[num[rt]] = 1;
}
for (int i = 1; i <= n; i ++ ) printf ("%d%c", ans[i], i == n ? '
' : ' ');
}
}
namespace subtask5 {//树的任意形态
struct UnionFindSet {//每个点的信息
int fa[N], fir, lst;
bool pre[N], nxt[N];
void build () {
for (int i = 1; i <= n; i ++ ) pre[i] = nxt[i] = false, fa[i] = i;
fir = lst = 0;
}
int find (int x) {
return x == fa[x] ? x : fa[x] = find (fa[x]);
}
bool same (int x, int y) {
return find (x) == find (y);
}
void merge (int x, int y) {
fa[find (x)] = find (y);
}
} t[N];
int dfs (int u, int f) {
int res = n + 1;
if (f && (!t[u].lst || t[u].lst == f) ) {//3.1
if (!t[u].nxt[f] && !(t[u].fir && ind[u] > 1 && t[u].same (f, t[u].fir)))//3.2,3.3
res = u;
}//判断终点
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].v, id = i >> 1;//id为这条边的编号
if (f == id) continue;
if (!f) {
if (!t[u].fir || t[u].fir == id) {//1.1
if (t[u].pre[id]) continue;//1.1
if (t[u].lst && ind[u] > 1 && t[u].same (t[u].lst, id)). continue;//1.2
res = min(res, dfs (v, id));
}
else continue;
}//判断起点
else {
if (t[u].fir == id || t[u].lst == f || t[u].same (id, f)) continue;//2.1,2.2
if (t[u].pre[id] || t[u].nxt[f]) continue;//2.3
if (t[u].fir && t[u].lst && ind[u] > 2 && t[u].same (t[u].fir, f) && t[u].same (t[u].lst, id)) continue;//2.4
res = min(res, dfs (v, id));
}
}
return res;
}
bool push (int u, int f, int end) {//删边（染色）
if (u == end) {
t[u].lst = f;
return true;
}
for (int i = head[u]; i; i = e[i].nxt) {
int id = i >> 1, v = e[i].v;
if (id == f) continue;
if (push (v, id, end)) {
if (!f) t[u].fir = id;//起点
else {
t[u].nxt[f] = t[u].pre[id] = true; ind[u]--;
t[u].merge(f, id);
}
return true;
}
}
return false;
}
void main () {
for (int i = 1; i <= n; i ++ ) t[i].build();
for (int i = 1; i <= n; i ++ ) {
int ret = dfs (p[i], 0);
push (p[i], 0, ret);
printf ("%d%c", ret, i == n ? '
' : ' ');
}
}
}
signed main(){
T = read();
while (T--) {
n = read();
Clear();
for (int i = 1; i <= n; i++) p[i] = read();
for (int i = 1, u, v; i < n; i++) {
u = read(), v = read();
x[i] = u, y[i] = v;
add_edge(u, v), add_edge(v, u);
ind[u]++, ind[v]++;
Max_In = max(Max_In, max(ind[u], ind[v]));
}
if(Max_In == n - 1) subtask2::main();
else if(Max_In == 2) subtask4::main();
else subtask5::main();
}
puts("");
return 0;
}