题目的“绝妙置换”定义较为复杂，我们无法直接进行转化。考虑列举出一些必要条件，从中寻找思路：
-
对于树上的一条边 \((x,y)\)，其中 \(x\) 为 \(y\) 的父节点。那么 \(x\) 在绝妙置换中的位置必定小于 \(y\) 的位置。
-
对于同个颜色节点的父亲集合，在绝妙置换中必定构成了一段前缀。
由此可以推出：\(\forall v_i,v_j\in v(i<j)\)，\(\{c_{son_{v_i}}\}\subseteq\{c_{son_{v_j}}\}\)。
通俗的讲，就是绝妙置换中位于前面的点相对于位于后面的点，必定满足它连向儿子的边的颜色集合完全包含了后面点的颜色集合。
如果仅仅只是这样，那么你将只能拿到少量的分数，因为这根本就组不成充分条件。考虑对第二个必要条件进行一些调整——我们新引入一个概念：子树完全包含。我们称子树 \(u\) 完全包含子树 \(v\) 当且仅当子树 \(v\) 能重叠在子树 \(u\) 上。换句话说，就是在子树 \(v\) 上添加一些点和边，使得子树 \(v\) 能变成子树 \(u\)。
所以我们现在将第二个必要条件由出边颜色集合转化为了子树完全包含，不妨重写一遍：\(\forall v_i,v_j\in v(i<j)\)，\(v_i\) 的子树完全包含 \(v_j\) 的子树。必要性的证明和修改前的证明类似。充分性通过归纳证明可得。
#include <bits/stdc++.h>
#define FL(i, a, b) for(int i = (a); i <= (b); i++)
#define FR(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
const int N = 2e5 + 10;
typedef vector<int> vc;
unordered_map<int, int> mp[N];
set<array<int, 3> > s[N]; vc ans, c, sz, e[N];
bool check(int x, int y){
for(auto u: mp[y])
if(!mp[x].count(u.first) || sz[mp[x][u.first]] < sz[u.second])
return 0;
return 1;
}
bool merge(int x, int y){
if(s[x].size() < s[y].size()) s[x].swap(s[y]);
for(auto u: s[y]){
auto it = (s[x].insert(u)).first, it2 = it;
if(it != s[x].begin())
if(!check(get<2>(u), get<2>(*--it2))) return 0;
if(++it != s[x].end())
if(!check(get<2>(*it), get<2>(u))) return 0;
}
return 1;
}
void dfs(int u){
s[u].insert({(int)e[u].size(), sz[u], u});
for(const int &v: e[u]){
if(mp[u].count(c[v])) ans[u] = 0;
mp[u][c[v]] = v;
}
for(const int &v: e[u]){
dfs(v); if(!ans[v] || !merge(u, v)) ans[u] = 0;
}
}
vc beechtree(int n, int m, vc p, vc co){
ans.resize(n, 1), sz.resize(n, 1), c.swap(co);
FR(i, n - 1, 1) e[p[i]].emplace_back(i), sz[p[i]] += sz[i];
dfs(0); return ans;
}