我们一直都创造着自己的人生，但是我们竟然一无所知。

ABC221F Diameter set

什么，为什么我连树的中心是什么都不知道？？

注意到，选出来的集合中的任意两个点都能构成直径。

设直径长度为 $\text{len}$。

• 如果直径为奇数。

  意味着，所有直径都必然会经过一个中心，而这个中心恰好是直径的中点（这显然可以通过反证法得到）。故考虑以这个点为根，对于所有儿子，找到每个儿子子树中深度为 $\frac{\text{len}+1}{2}$ 的点的个数，乘法原理乘起来即可。

• 如果直径为偶数。

  意味着所有直径都会经过直径最中间的边（证法如上），对于最中间的边对应的 $(u,v)$，分别找到 $u,v$ 对应的子树中，深度为 $\frac{\text{len}}{2}$ 的点的个数，乘起来即可。

感觉很简单啊，我大抵是没睡醒吧。

ARC103F Distance Sums

最开始想歪了，想着从重心出发往下，发现根本做不了。

实际上，你将 $a_i$ 从大到小排序之后，注意到 $a_i$ 最小的一定是重心，然后把它当作根节点。

那么 $a_1$ 一定是叶子，并且对于所有的 $j>i$，$j$ 不可能是 $i$ 的儿子。

也就是说，如果我们确定了 $j\in[1,i - 1]$ 的位置和边，那么我们就可以知道 $\text{siz}_i$ 和他的所有儿子。

故考虑排完序之后，从 $1\to n$，从小到大枚举，假设我们知道了 $[1,i]$ 中所有点的 $\text{siz}$，那么我们也可以确定他们父亲的大小（且父亲的 $\text{D}$ 一定比自己大，这是重心为根的性质，由于 $D$ 互不相同，我们也就确定了他们的父亲），也就可以确定 $[1,i+1]$ 所有点的 $\text{siz}$ 和父亲。

然后我们知道 $a_1$ 是叶子，类似一个归纳的过程，这个题就解决了，最后把图建出来检验一下即可。

感觉关键在于 父亲 $\to$ 儿子不好做，但是儿子 $\to$ 父亲好做。就还是要对 $n-2\times \text{siz}_x$ 这个 $x$ 放更多的关注。

CF1919D 01 Tree

注意到我们可以从下往上，这样不会影响其他的点，发现每次可以将两个兄弟叶子，如果满足 $|a_i-a_{i-1}|=1$，其实可以把这两个点删掉，只留他们的父亲。

转化之后可以得到，题目相当于求解是否可以每次找到一个 $i\in[2,n]$，满足 $|a_i-a_{i-1}|=1$，将 $a_i,a_{i-1}$ 删掉，变成 $\min (a_i,a_{i-1})$，将整个数组变成 $[0]$。

其实很好做，考虑先把数组中的 $0$ 去掉，会发现被分成了两段，这两段都需要通过操作得到 $[1]$，然后我们对于两段分别考虑递归，通过里面的 $1$ 去掉之后，会分成若干段，每段我们需要得到 $[2]$，然后以此类推。 直到 $l=r$ 时，判断 $a_l$ 是否是我们想得到的值即可。

大致就是：

bool solve(int l, int r, int k)
{
	if(r < l) return true;
	if(l == r) return a[l] == k;
	int id = lower_bound(p[k].begin(), p[k].end(), l) - p[k].begin();
	if(id >= p[k].size()) return false;
	if(p[k][id] > r) return false;
	vector<int> q;
	while(id < p[k].size() && p[k][id] <= r) q.push_back(p[k][id]), id++;
	int last = l;
	for (int i = 0; i < q.size(); ++i)
	{
		if(!solve(last, q[i] - 1, k + 1)) return false;
		last = q[i] + 1;
	}
	return solve(last, r, k + 1);
}
solve(1, n, 0);//其中 p[i] 是 a[j] = i 所有的 j 的一个 vector

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

ARC097F Monochrome Cat

会一个换根的做法，但是感觉跟今天的性质题不太契合，所以没有去写。

其实也没有那么难吧。

首先先考虑必须走回起点如何计算答案。

先去掉所有为黑色的子树，保证叶子都是白色，发现经过 $2n-2$ 步之后，每个点被改变的次数就是 $\text{deg}_i$，答案还要加上改变之后为白色的点的个数。

然后考虑不回到起点，也就是有一条链只走一遍的情况。

考虑分析这条链上点 $i$ 经过 $\text{deg}_i$ 次操作之后：

• 如果是白色，那么少了一次操作之后，就是黑色，会对总答案减少 $2$ 的贡献。
• 如果是黑色，那么少了一次操作之后，就是白色，不会对总答案造成影响。

题目转化为找到一条白色点最多的链，其实就是树上直径。

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

感觉是要学会去弱化条件，并去除一些无关变量。

CF1804F Approximate Diameter

感觉好神，看到这个不等式完全没思路最开始。

一个经典（？的结论，对于图上的任意一个节点 $x$，设他到其他节点的最大距离为 $y$，那么一定满足 $\frac{d(G_i)}{2}\le y\le d(G_i)$。证明其实没有那么困难：

• 如果 $y$ 是图的直径上的点，到端点的距离显然满足条件。
• 如果 $y$ 不是直径上的点，它必然可以先走到直径上再走到更远的端点。

也就是说，我们随便钦定一个点（比如 $1$）输出距离它最远的点即可。

但是这样的复杂度仍然是 $\mathcal{O}((n+m)q\log n)$。

发现上界非常宽松，是 $2\times d(G_i)$。观察到答案是单调递减的，假设最开始答案是 $x$，当前答案是 $s$，只有当 $x>2\times s$ 时 $x$ 才会无效，也就是说 $x$ 可以作为答案直到这样条件的 $s$ 出现。发现每出现这样的 $s$，对应的 $x$ 就会减半，最多只有 $\log $ 个，且可以二分快速找到这样的 $s$，时间复杂度 $\mathcal{O}((n+m)\log ^2 n)$。

感觉是很典型的对于 $\frac{1}{2}$ 和 $2$ 的处理，找中点和数量级的特点。

ARC156C Tree and LCS

学会去关注上下界是非常基本的素养。

发现我们似乎公共子序列最多长度只有 $1$。

也就是说，每条路径上，和其对应的 $p$，相同的数中，这个序列正好是反过来的。

看一下如何构造。

考虑从叶子节点出发，发现我们可以选取任意两个叶子节点，将他们的权值交换，就可以使他们自己构成的序列不会对答案造成任何影响。

然后把这两个叶子删掉，那么就会有新的叶子形成，重复以上过程，发现得到的正好就是满足条件的方案。

反证法可以证明，这样不可能存在长度 $\ge 2$ 的公共子序列。