CF1610H 题解

First Post:

Last Update:

之前一直没有一个想贪心的方法论，这道题提供了一种思路。

容易发现，第一次操作根节点之后，剩下的链都是祖先-后代链。先假设在根节点为 的时候全是祖先-后代的链，那么考虑对于一条祖先-后代链怎么选更优，显然如果能选的话，我们会尽量选深度更小的点，这样就可以满足一些更浅的祖先-后代链的限制。设一条链 ，其中 ，设 为这条链中深度为 的那个点，那么选 肯定是最优的。只不过可能会出现，更深的链的 已经满足了更浅的链的限制，那么我们把所有 按照深度从大到小排序，每次如果这个 还没有被覆盖就选它。容易理解这种贪心的正确性。其实，如果树是一条链的话，这个问题就对应到：在数轴上选一些点使得每个区间中都有选中的点，这是经典问题。

回顾上述的贪心过程，我们发现其大概分为两步：一步是考察一条链怎么选能尽量满足其它部分的限制，即局部最优解，一步是确定 贪心的顺序。顺序怎么确定呢？按照限制满足的方向来确定。上例中，更深的链选点可以满足更浅的链的限制，所以按照从深到浅来贪心。为什么限制满足的方向一定是从深到浅，好像从浅到深也能套进上面那段话？实质上是因为两条祖先-后代链的交会处肯定是某条链的较浅段，所以段内尽量往浅了选。从而方向也是从深到浅。

接下来考虑加入了非祖先-后代链的情况。实际上，在上文的贪心中，尽量选更浅的点也能尽量满足非祖先-后代链。更具体地，如果按照深度从小到大排列所有的 ，我们选出的肯定是满足限制的，字典序最小的一组 ，从而这一组解已经最优地满足了非祖先-后代链的限制。也就是说，我们在选完那些 之后，如果还有非祖先-后代链没有消去，答案就 （操作一次根），否则直接输出答案即可。

使用 BIT 维护单点加与子树和即可。时间复杂度为 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <bits/stdc++.h>
using namespace std;

namespace FastIO {
	#define iL (1 << 20)
	char ibuf[iL],*iS = ibuf + iL,*iT = ibuf + iL;
	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread(ibuf,1,iL,stdin),iS == iT ? EOF : *iS++) : *iS++)
	template<typename T>
	inline void read(T &a)
	{
		char ch;int sign = 0;
		for(ch = gc();!isdigit(ch);ch = gc())
			if(ch == '-') sign = 1;
		a = ch & 15;
		for(ch = gc();isdigit(ch);ch = gc())
			a = (a << 3) + (a << 1) + (ch & 15);
		if(sign) a = -a;
	}
	char Out[iL],*iter = Out;
	#define flush() fwrite(Out,1,iter - Out,stdout),iter = Out
	template<typename T>
	inline void write(T x,char end = '\n')
	{
		int c[40],l = 0;if(x < 0) *iter++ = '-',x = -x;
		do c[++l] = x % 10,x /= 10; while(x);
		while(l) *iter++ = c[l--] + '0';
		*iter++ = end;flush();
	}
	#undef iL 
	#undef gc
	#undef flush
}
using namespace FastIO;

const int N = 3e5 + 5,Lg = 19;
int n,m;
vector<int> G[N];
int U[N],V[N],nd[N];
int L[N],R[N];
int tr[N];
#define lowbit(x) (x&(-x))
inline void upd(int x,int v) { for(int i = x;i <= n;i += lowbit(i)) tr[i] += v;}
inline int Sum(int x) { int res = 0;for(int i = x;i;i ^= lowbit(i)) res += tr[i];return res;}
inline int Qry(int x) { return Sum(R[x]) - Sum(L[x] - 1);}
int anc[Lg][N],dep[N];
void dfs0(int x,int f) {
	anc[0][x] = f;L[x] = ++L[0];
	dep[x] = dep[f] + 1;
	for(int i = 1;i < Lg;i++) anc[i][x] = anc[i - 1][anc[i - 1][x]];
	for(auto y : G[x])
		if(y != f) dfs0(y,x);
	R[x] = L[0];
}
int lca(int x,int y) {
	if(dep[x] < dep[y]) swap(x,y);
	for(int i = Lg - 1;i >= 0;i--)
		if(dep[anc[i][x]] >= dep[y])
			x = anc[i][x];
	if(x == y) return x;
	for(int i = Lg - 1;i >= 0;i--)
		if(anc[i][x] != anc[i][y])
			x = anc[i][x],y = anc[i][y];
	return anc[0][x];
}
int jump(int x,int y) {
	for(int i = Lg - 1;i >= 0;i--)
		if(dep[anc[i][x]] > dep[y])
			x = anc[i][x];
	return x;
}
int srt[N],tot;
int crs[N],t2;
int main() {
	read(n);read(m);
	for(int i = 2,x;i <= n;i++)
		read(x),G[x].push_back(i);
	dfs0(1,0);
	for(int i = 1;i <= m;i++) read(U[i]),read(V[i]);
	for(int i = 1;i <= m;i++) {
		int p = lca(U[i],V[i]);
		if(dep[U[i]] > dep[V[i]]) swap(U[i],V[i]);
		if(p == U[i]) {
			if(dep[V[i]] == dep[U[i]] + 1) return puts("-1"),0;
			nd[i] = jump(V[i],U[i]);
			srt[++tot] = i;
		} else crs[++t2] = i; 
	}
	sort(srt + 1,srt + tot + 1,[&](const int &x,const int &y) { return dep[nd[x]] > dep[nd[y]];});
	int ans = 0;
	for(int i = 1;i <= tot;i++) {
		int id = srt[i];
		if(Qry(nd[id]) - Qry(V[id]) > 0) continue;
		else ++ans,upd(L[nd[id]],1);
	}
	int flg = 0;
	for(int i = 1;i <= t2;i++)
		if(Qry(U[crs[i]]) + Qry(V[crs[i]]) == ans) flg = 1;
	cout << ans + flg << endl;
	return 0;
}
≡