自动搬运

查看原文

来自洛谷，原作者为

	zac2010 a vegedog

搬运于2025-08-24 22:50:01，当前版本为作者最后更新于2023-10-02 21:59:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目的“绝妙置换”定义较为复杂，我们无法直接进行转化。考虑列举出一些必要条件，从中寻找思路：

• 对于树上的一条边 $(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$ 的子树。必要性的证明和修改前条件二的推导过程类似。两个条件的充分性通过归纳证明不难得到。

第一个条件可以直接用一个哈希表判断；第二个条件的判断，考虑用一个 set 记录子树中的顺序（优先级：第一关键字为出边颜色数，第二关键字为子树大小，第三关键字为树上节点的编号大小），启发式合并时判断一下即可。

#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;
}