[AHOI2022] 回忆

题目背景

生活在题面里的他们，是一群怪异的少年。

对城市中修建道路需满足的基本物理限制熟视无睹，沉迷于十万个城市、百万条道路上的各种结构。

明明知道真正需要的数字庞大到无法计算，却偏要关心它模一个奇怪素数之后得到的结果。

如此智力超群的他们，却总是在自己提出的诡异的问题下败下阵来，把它们一股脑地丢给你们来做。

如今，他们长大了。他们学习到更普适的理论，习惯了更抽象的符号，不必再思考如此古怪的问题。但他们不曾料到，你们却以这些 “无用” 的问题为驱动，于计算机学科体系的一隅，开垦出了一片独属于 OI 的新天地。

有一天，他们各自回忆起了少年时期提出的问题。

题目描述

少年时，他们提出了 \(n\) 个问题，从 \(1\) 到 \(n\) 编号。一个问题总由一个更基础的问题衍生而来，因此问题之间构成了一个树形的结构：\(1\) 号问题是最基本的问题，也就是树的根节点，而其他问题都由其父亲节点对应的问题衍生而来。如果两个问题在树上相邻，则称这两个问题彼此相关。

少年时期的他们一共做了 \(m\) 次研究，第 \(i\) 次的研究从提出较为基本的问题 \(s_i\) 开始，将它不断地修改、推广，最终提出问题 \(t_i\)。这些研究满足 \(s_i \ne t_i\) 且 \(\bm{s_i}\) 必定是 \(\bm{t_i}\) 的祖先。即使研究的问题完全相同，从不同的角度研究会有不同的结果，因此可能存在 \(\bm{i \ne j, (s_i, t_i) = (s_j, t_j)}\) 的情形。

现在，他们正一轮轮地回忆着少年时提出的问题。在他们每一轮对问题的回忆中，他们首先回忆到 \(n\) 个问题中的任意一个。接下来，如果存在与当前回忆到的问题彼此相关且在这轮回忆中没有被回忆到的问题，那么他们可以将思绪从当前问题上切换到这些问题中的任意一个，并回忆到这个新的问题。他们可以不断地切换思绪，也可以在回忆到任何一个问题之后结束回忆。每一轮回忆是独立的，也就是说一个问题可以被多轮回忆回忆起。

如果在某一轮回忆中，他们同时回忆到了问题 \(s_i\) 和问题 \(t_i\)，则称第 \(i\) 次研究被想起。

为了更好地理解上述概念，考察以下例子：\(n = 5\)，问题 \(1\) 与问题 \(2, 3\) 相关，问题 \(3\) 与问题 \(4, 5\) 相关。一轮可能的回忆是：从问题 \(2\) 开始回忆，切换思绪到问题 \(1\)，再切换到问题 \(3\)，最终切换到问题 \(5\) 并结束回忆。如果 \(m = 4\)，\((s_1, t_1) = (1, 2), (s_2, t_2) = (1, 4), (s_3, t_3) = (s_4, t_4) = (3, 5)\)，那么这轮回忆会让第 \(1\) 次、第 \(3\) 次和第 \(4\) 次研究被想起，而第 \(2\) 次研究不会被想起。

他们问你们的最后一个问题是：如果每轮回忆的起点以及思绪的切换可以任意选择，最少需要多少轮回忆才能使所有的研究都被想起。

输入格式

本题有多组测试数据。输入的第一行包含一个正整数 \(T\)，表示数据组数。

对于每组测试数据，第一行包含两个正整数 \(n, m\)，分别表示问题的个数和研究的个数。

接下来 \(n - 1\) 行每行包含两个正整数 \(u_i, v_i\)，表示问题 \(u_i\) 与问题 \(v_i\) 相关。

接下来 \(m\) 行每行包含两个正整数 \(s_i, t_i\)，描述一次研究。

输出格式

对于每组测试数据输出一行一个正整数，表示他们最少需要回忆的轮数使得 \(m\) 次研究均被想起。

样例 #1

样例输入 #1

样例输出 #1

2
2

提示

【样例解释 #1】

样例中的第一组数据与题目描述所给的例子相同。一种可能的回忆方案为：

第一轮回忆中，从问题 \(2\) 开始，依次切换思绪到问题 \(1, 3, 5\)。此时第 \(1, 3, 4\) 次研究被想起，但第 \(2, 5\) 次没有。
第二轮回忆中，从问题 \(4\) 开始，依次切换思绪到问题 \(3, 1\)。此时第 \(2, 5\) 次研究被想起。

第二组数据符合特性 A 的要求。一种可能的回忆方案为：第一次回忆依次回忆到 \(2, 1, 3, 5, 6\)，第二次回忆依次回忆到 \(8, 7, 9, 10\)。

【样例 #2】

见附件中的 memory/memory2.in 与 memory/memory2.ans。

这组数据满足了测试点 \(1 \sim 4\) 的条件。

【样例 #3】

见附件中的 memory/memory3.in 与 memory/memory3.ans。

这组样例满足了特性 A 的条件。且除了后 \(3\) 组数据外，其余样例均满足 \(n, m \le 1000\)。除了后 \(30\) 组数据外，其余样例均满足 \(n, m \le 30\)。你也可以用这组样例完成对较小规模数据的测试。

【样例 #4】

见附件中的 memory/memory4.in 与 memory/memory4.ans。

这组样例满足了测试点 \(24 \sim 25\) 的条件。同样例 #3，本样例满足：除了后 \(3\) 组数据外，其余样例均满足 \(n, m \le 1000\)。除了后 \(30\) 组数据外，其余样例均满足 \(n, m \le 30\)。你也可以用这组样例完成对较小规模数据的测试。

【样例 #5】

见附件中的 memory/memory5.in 与 memory/memory5.ans。

这组样例满足了特性 B 的条件。

【样例 #6】

见附件中的 memory/memory6.in 与 memory/memory6.ans。

这组样例满足了特性 C 的条件。

【评分方式】

对于每一组测试点，如果你的输出格式正确，且每一组数据输出的答案正确，那么你会获得 \(4\) 分。

否则，如果你的输出格式正确，且对于每一组数据，你输出的答案与正确答案相等或者比正确答案大 \(\bm{1}\)，那么你将在此测试点上获得 \(3\) 分。

【数据范围】

本题共 \(25\) 个测试点。对于所有的测试点，\(1 \le n, m \le 2 \times {10}^5\)，\(1 \le \sum n, \sum m \le 5 \times {10}^5\)，\(1 \le u_i, v_i, s_i, t_i \le n\)，\(s_i \ne t_i\)。保证输入的 \((u_i, v_i)\) 构成一棵树，\(s_i\) 在以 \(1\) 为根的树上是 \(t_i\) 的祖先。

测试点	规模限制	特殊性质
\(1 \sim 4\)	\(T \le 3000\)，\(n \le 50\)，\(m \le 15\) 且最多有 \(5\) 组数据满足 \(m \ge 10\)	无
\(5 \sim 6\)	\(n, m \le 100\)，\(\sum n^3, \sum m^3 \le 3 \times {10}^7\)	A
\(7\)	\(n, m \le 100\)，\(\sum n^3, \sum m^3 \le 3 \times {10}^7\)	B
\(8\)	\(n, m \le 100\)，\(\sum n^3, \sum m^3 \le 3 \times {10}^7\)	C
\(9\)	\(n, m \le 100\)，\(\sum n^3, \sum m^3 \le 3 \times {10}^7\)	无
\(10 \sim 11\)	\(n, m \le 1000\)，\(\sum n^2, \sum m^2 \le 3 \times {10}^7\)	A
\(12\)	\(n, m \le 1000\)，\(\sum n^2, \sum m^2 \le 3 \times {10}^7\)	B
\(13\)	\(n, m \le 1000\)，\(\sum n^2, \sum m^2 \le 3 \times {10}^7\)	C
\(14 \sim 16\)	\(n, m \le 1000\)，\(\sum n^2, \sum m^2 \le 3 \times {10}^7\)	无
\(17 \sim 18\)	\(n, m \le 2 \times {10}^5\)，\(\sum n, \sum m \le 5 \times {10}^5\)	B
\(19 \sim 20\)	\(n, m \le 2 \times {10}^5\)，\(\sum n, \sum m \le 5 \times {10}^5\)	C
\(21 \sim 23\)	\(n, m \le 2 \times {10}^5\)，\(\sum n, \sum m \le 5 \times {10}^5\)	A
\(24 \sim 25\)	\(n, m \le 2 \times {10}^5\)，\(\sum n, \sum m \le 5 \times {10}^5\)	无

特殊性质 A：保证 \(n\) 为偶数，且树的结构为：对于任意正整数 \(1 \le i \le \lfloor \frac{n}{2} \rfloor\)，\(2 i\) 的父亲为 \(2 i - 1\)；若 \(i \ge 2\)，则 \(2 i - 1\) 的父亲为 \(2 i - 3\)。
特殊性质 B：保证对于所有的正整数 \(1 \le i \le m\)，\(s_i\) 为 \(t_i\) 的父亲。
特殊性质 C：保证对于所有的正整数 \(1 \le i \le m\)，\(s_i = 1\)。

请注意，测试点的难度与编号并没有直接关系。

【提示】

请注意，为了取得部分分，你必须保证输出格式正确，即：输出恰好有 \(m\) 行，且每行是一个正整数。

此外，如果某组测试数据中你输出的结果比答案小 \(1\) 而不是大 \(1\)，那么你不能在该测试点获得 \(3\) 分。

本题部分测试点读入量较大。为了优化程序的总运行时间，我们建议你采用较为快速的读入方式。

题解

转自 AHOI2022 回忆 - 自下向上之一 - feecle6418 的博客 - 洛谷博客 (luogu.com.cn) CCCCCCCOrz

因为树上贪心一定要从下往上，考虑从下往上贪心。每个点只保留深度最浅的以其为下端点的限制。

称路径为直上直下的路径；称两条路径匹配为它们能连接起来成为一条路径。

首先，找出所有子树内没有限制下端点，自身又是限制下端点的点，

容易证明：一定存在一种最优方案，所有路径的端点都属于这些点。

我们的目标是尽量少开始路径，尽量多匹配路径。

考虑在 \(x\) 子树内有哪些路径：

尚未达到自己目标深度的路径。
已经达到目标深度，可以匹配的路径。
已经与匹配的有上有下的路径。

\(1\) 类路径只需要特殊处理目标深度最小的这一条，这一条可以用来满足 \(x\) 到 \(1\) 这条链上其它的限制；其它 \(1\) 类路径在达到目标深度后会自动变成 \(2\) 类路径，可以在深度上打标记实现。

\(2,3\) 类路径可以互相转化（可以把 \(3\) 拆成两个 \(2\)）。合并两个子树 \(p,q\) 时，贪心匹配它们内部的路径。假设 \(p,q\) 分别 2 类路径数为 \(x,y\)，\(3\) 类路径数为 \(a,b\)。

发现肯定是用 \(x,y\) 小的那一边去匹配大的那一边（因为把内部 \(3\) 类路径拆开拿来匹配并不会增加答案）。不妨假设 \(x<y\)。

\(x+2a\ge y\)：此时可以完全配对，根据奇偶性至多留下一条路径。
\(x+2a < y\)：会剩下 \(y-(x+2a)\) 条路径。

合并完子树后，处理 \(x\) 自己开始的贡献。

如果 \(x\) 子树内还有 \(1\) 类路径没有完结，根据上面的说法，它就是拿来处理这里新加这条这样的路径的。故直接把这条路径拉长。

否则，我们不得不新开一条路径来满足 \(x\) 本身的要求。我们可以直接拿出一条 \(2\) 类路径，或拆掉一条 \(3\) 类路径。如果 \(2,3\) 类路径都没有就不得不新开一条路径。（注意！“新开路径”并没有显示在算法中体现，因为我们是在它完成自己任务之后才把它作为可以匹配的路径加进来的，这也是贪心算法的前提。所以，现在这里新开路径不需要做其它操作；反而是拉长一条原本有的路径需要把当前贡献减一。）

整个做法时间复杂度 \(O(n+m)\)。

以下瞎扯一下正确性。这个算法自己有一些非常让人信服的点。

注意到每个限制我们尽量在深的地方拿出来配，越深配在之后能做的事情越多。
算法的部分内部都显然正确。
整个过程完全从下往上，符合“树上一定要从下往上而非从上往下”的教训（应该叫经验）。

#include<bits/stdc++.h>
#define N 200010
using namespace std;
int T,n,m,a[N],b[N],d[N],mn[N],tag[N],v[N];
vector<int>g[N];
int read(){
    int x = 0,f = 1;
    char ch = getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f = -1;
        ch = getchar();
    }
    while(ch>='0'&&ch<='9'){
        x = x*10+ch-'0';
		ch = getchar();
	}
    return x*f;
}
void dfs1(int x,int fa){
	d[x] = d[fa]+1;
	for(int y:g[x]){
		if(y==fa) continue;
		dfs1(y,x);
	}
}
void dfs2(int x,int fa){
	for(int y:g[x]){
		if(y==fa) continue;
		dfs2(y,x);
		b[y]+=tag[d[x]];
		tag[d[x]] = 0;
		if(mn[y]==d[x]){
			b[y]++;
			mn[y] = 0;
		}
		if(mn[x]&&mn[y]){
			if(mn[x]<mn[y]) tag[mn[y]]++;
			else{
				tag[mn[x]]++;
				mn[x] = mn[y];
			}
		}else mn[x]|=mn[y];
		if(b[x]<b[y])swap(b[x],b[y]),swap(a[x],a[y]);
		if(b[y]+2*a[y]>=b[x]){
			int w = b[x]+b[y]+2*a[y];
			a[x]+=(w>>1);
			b[x] = (w&1);
		}else{
			b[x]-=b[y]+2*a[y];
			a[x]+=b[y]+2*a[y];
		}
		
	}
	if(v[x]){
		if(!mn[x]){
			mn[x] = v[x];
			if(b[x])b[x]--;
			else if(a[x]) a[x]--,b[x]++;
		}else mn[x] = min(mn[x],v[x]);
	}
}
int main(){
	T = read();
	while(T--){
		n = read();m = read();
		for(int i = 1;i<n;i++){
			int x,y;
			x = read();y = read();
			g[x].push_back(y);g[y].push_back(x);
		}
		dfs1(1,0);
		for(int i = 1;i<=m;i++){
			int x,y;
			x = read();y = read();
			if(!v[y]||v[y]>d[x]) v[y] = d[x];
		}
		dfs2(1,0);
		printf("%d\n",a[1]+b[1]);
		for(int i = 1;i<=n;i++)
			mn[i] = tag[i] = v[i] = a[i] = b[i] = 0,g[i].clear();
	}
	return 0;
}