成功拿下最短解 $+$ 最优解，爽。

题意

给定一棵 $n$ 个点的有根树，需要选择编号为一个区间 $[L,R]$ 的点满足 $m$ 个限制：$p_i$ 的所有 $k_i$ 级儿子中要被选择至少一个。求长度最小条件下 $L$ 最小的 $[L,R]$。

思路

把这个树按照深度对齐画出来，发现每个要求形如要选择同一层上的一个区间，其实也就是把 bfs 序按照顺序求出来在上面选区间，要求出一个区间和所有区间都有交。

其实这个我不会做，我以为做不了，于是我想再找一些性质。

注意到这些区间之间不是没关系就是包含关系，而所有大区间都可以扔掉。这说明什么？说明每个点至多被一个区间包含！

问题又变成啥了？我们给每个点染色，求最短的区间使得包含所有颜色。

这个是不是双指针板子题来着。好的现在我们来看看如何找到包含每个点的最小区间。

我们不要刚刚的 bfs 序。我们给每个区间我们直接 dfs，并记一个 $\text{id}_{\text{dep}}$ 维护在当前包含深度为 $dep$ 的点的最小区间。对于每个点 $x$ 我们做以下操作：

1. 把 $x$ 的颜色设为 $\text{id}_{\text{dep}_x}$。

2. 遍历所有 $p_i=x$ 的限制，看看 $\text{id}_{\text{dep}_x+k_i}$ 是否为空。如果有值说明有个大区间在上面，可以被扔掉了。注意有可能这个大区间已经给其他点染过颜色了，要记得在最后清空。

3. 然后把 $\text{id}_{\text{dep}_x+k_i}$ 设为 $i$。

4. dfs 所有儿子。

5. 把所有涉及过的 $\text{id}$ 清空。

时间复杂度 $O(n)$。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m, dep[200002], id[200002], col[200002], cnt[200002], kd, ansl = 0x3f3f3f3f3f3f3f3f, ansi;
bool f[200002];
vector<ll> son[200002];
vector<pair<ll, ll> > tsk[200002];
void dfs(ll x) {
	col[x] = id[dep[x]];
	for (auto i : tsk[x]) {
		if (id[dep[x] + i.second]) f[id[dep[x] + i.second]] = 1, m --;
		id[dep[x] + i.second] = i.first;
	}
	for (ll y : son[x]) dep[y] = dep[x] + 1, dfs(y);
	for (auto i : tsk[x]) id[dep[x] + i.second] = 0;
}
int main() {
	cin >> n;
	for (ll i = 2, p; i <= n; i ++ ) cin >> p, son[p].push_back(i);
	cin >> m;
	for (ll x, y, i = 1; i <= m; i ++ ) cin >> x >> y, tsk[x].push_back({i, y});
	dep[1] = 1;
	dfs(1);
	for (ll i = 1; i <= n; i ++ ) if (f[col[i]]) col[i] = 0;
	for (ll i = 1, j = 1; i <= n; i ++ ) {
		while (j <= n && kd < m) {
			if (col[j]) kd += !(cnt[col[j]] ++); j ++;
		}
		if (kd == m && (j - i) < ansl) ansl = j - i, ansi = i;
		if (col[i]) kd -= (!(-- cnt[col[i]]));
	}
	cout << ansi << " " << ansi + ansl - 1;
}