万物皆有裂痕，那是光照进来的地方。

ARC183D Keep Perfectly Matched

我们考虑如何去刻画有完美匹配这个东西。

注意到对于点 $x$ 的子树，如果大小为奇数，那么意味着 $x$ 一定会和他的父亲节点匹配。反之，如果是偶数就会与自己的某个子结点配对。

那么发现存在完美匹配的充要条件如下：

• 对于所有的 $x$，如果其子树大小为奇数，由于他会与自己的父亲配对，故他的所有儿子的子树大小必然是偶数。
• 对于子树大小为偶数的 $x$，它必然会与某个子结点配对，也就是说，他的儿子里面，有且仅有一个儿子的子树大小为奇数。
• 特别的，根的子树大小为偶数。

刻画出完美匹配的情况下，我们考虑如何删，即看哪些叶子删了不会影响答案。

注意到如果我们删掉 $x$，会把 $x\to$ 根节点 路径上的所有点的大小奇偶性取反。如果路径上存在边 $(x,y)$，且 $x,y$ 的子树大小均为偶数，那么取反之后变成两个奇数，显然违背了我们刚才完美匹配的条件。

也就是说，路径上所有点，子树大小的奇偶性必须是交替出现的。

再接着考虑如何删两个点，发现必然是在根的两个不同子树下，且一个子树大小是奇数，一个是偶数，在两颗子树中分别找到路径奇偶性交替出现的叶子， 删掉就是合法的。

故我们可以构造出每个根的子树下，叶子节点的删除顺序，保证每次路径奇偶交替即可。

可以考虑一定条件的后序遍历，不是很好讲，见片段代码：

vector<int> p[maxn];
void dfs(int x, int last, int belong)
{
	if(siz % 2 == 0)
	{
		for (int i = fst; i; i = arr[i].nxt)
		{
			int j = arr[i].tar;
			if(j == last) continue;
			if(siz[j] & 1) dfs(j, x, belong);
		}
	}
	for (int i = fst; i; i = arr[i].nxt)
	{
		int j = arr[i].tar;
		if(j == last) continue;
		if(siz[j] % 2 == 0) dfs(j, x, belong);
	}
	p[belong].push_back(x);
}

为了防止子树不平均无法实现刚刚操作的情况，我们钦定根为树的重心，本质就是保证每次删完之后重心不变，我们就可以保证能一直删下去。显然就是每次选取当前奇数大小和偶数大小最大的子树，分别根据我们求出来的删除顺序选一个点删掉即可。

时间复杂度 $\mathcal{O}(n)\backsim \mathcal{O}(n\log n)$。

学到的是，看到匹配这种东西，尤其是在树上，一定去想不管是深度还是大小的奇偶性会不会对解决问题有所启发。

ARC095F Permutation Tree

感觉刻画的不是特别清楚，差点意思。

求出 $p$ 的逆排列 $q$，即 $q_{p_i}=i$。发现连边本质就是对于所有的 $i$，由 $q_i$ 向前缀最大值连边。

本质上就是，对于所有的前缀最大值的位置 $t_1,t_2,...,t_k$，对于所有的 $i\in (t_{j-1},t_j)$，$q_i\to t_{j-1}$，然后 $t_j\to t_{j-1}$。可以发现，这很像一个毛毛虫的形式，在一条链外面连了一些点。

可以进一步发现，所有的前缀最大值都在树的直径上，其他的叶子节点，就是中间的不是前缀最大值的节点。

然后根据字典序最小和前缀最大值的限制，一个一个往里面填位置就可以了。

注意直径有两端，都要拿出来跑一遍。

时间复杂度 $\mathcal{O}(n)$。

感觉最开始刻画的不够清晰。

AGC024D Isomorphism Freak

直接粘题解了：

我们发现其实最终所得的树只有两种，一种是以一条边为中心，左右两边同构，一种是以点为中心，呈放射状分布。

其实这两种都一样，以边为放射状的只要把这条边看成一个点就可以了。

这样我们考虑枚举中心，要求其权值，首先不难发现同构的数量其实就是以中心为根的树的深度。然后我们考虑叶子个数，我们只要想想构造这棵树的过程，其实就是把每一层深度的所有点的儿子数补成相同，那么补完后树的叶子个数就是每层非叶子节点儿子个数的乘积，对于原树来讲就是每层儿子树最多的儿子个数的乘积。

感觉同构类问题，要向直径这个方面去想（其实也可以是重心这个点）。