考虑到造数据的人为了使得叶子很多，树高不会很大。

然而我赛时并没有考虑到。判了一堆东西，却只得了75分。

这是一篇非正解的题解

首先有一个很显然的贪心，每一次把红棋移动到最近的叶子上，然后如果蓝棋此时没走到叶子就回到蓝棋，答案加一。

所以每棵子树是独立的，设计 $dp_u$ 表示子树 $u$ 的答案，初始 $dp_u=1$。

然后我们容易求出每个点与最近的叶子距离，记为 $lst_u$，于是，如果想使用 $dp[u]=\max(dp[u],dp[v]+1)$ 的前提是 $dep_u+lst_u<=dep_v$，但是考虑到父亲的答案一定不比儿子劣，因为有更多可能性。所以 $dep_u+lst_u=dep_v$。

然后维护 $mx[u][h]$ 表示 $u$ 往下 $h$ 距离中 $dp$ 值的最大值，这个可以 $\Theta(h)$ 转移。

总复杂度为 $\Theta(nh)$，其中 $h$ 为树高。

代码

代码长度为赛事代码的40%

#include<bits/stdc++.h>
#define int long long
#define R(x) x=read()
using namespace std;
inline int read() {
	int x=0,y=1;
	char e=getchar();
	while(e>'9'||e<'0') {
		if(e=='-')y=-1;
		e=getchar();
	}
	while(e>='0'&&e<='9') {
		x=(x<<3)+(x<<1)+(e^'0');
		e=getchar();
	}
	return x*y;
}
const int N=200005;
int n;
vector<int>G[N];
int dp[N],lst[N],dep[N],cnt[N];
int mx[N][55];
void DP(int u) {
	if(u!=1&&G[u].size()==1) {
		lst[u]=0;
		return ;
	}
	for(auto v:G[u]) {
		if(dep[v])continue;
		dep[v]=dep[u]+1;
		DP(v);
		lst[u]=min(lst[u],lst[v]+1);
		mx[u][dep[v]]=max(mx[u][dep[v]],dp[v]);
		for(int i=0; i<=50; ++i) {
			mx[u][i]=max(mx[u][i],mx[v][i]);
		}
	}
	if(lst[u]+dep[u]<=50) dp[u]=max(1ll,mx[u][lst[u]+dep[u]]+1);
}
signed main() {
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	R(n);
	for(int i=2,f; i<=n; ++i) {
		R(f);
		G[i].push_back(f);
		G[f].push_back(i);
	}
	int cnt=0;
	for(int i=2; i<=n; ++i) {
		if(G[i].empty())++cnt;
	}
	if(cnt==1) {
		cout<<"1\n";
		return 0;
	}
	memset(lst,0x3f,sizeof lst);
	dep[1]=1;
	DP(1);
	cout<<max(1ll,dp[1]);
	return 0;
}

赛时唯一切出来的一道题

想了我 3.5 h 头要裂开了

众所周知 OIer 写题解一般会比较注重怎么想到（非常人性，不像什么注意力上长个人的数学佬），而不是严谨证明

题意

• 给一颗树，根节点有红蓝两色棋各一个
• 蓝棋向任意一个儿子移动，如果到达叶子，游戏结束
• 红棋在蓝棋每次移动后也向任意一个儿子移动，若到达叶子节点，则在这个叶子上放一个红棋，同时把原来的红棋放到蓝棋所在的节点
• 问游戏结束时，树上最多有几个红棋

$1<=n<=2e5$

引入

简单分析一下题意就会发现这个题是不可以直接贪心的（不证，随便构造一个就是反例）

我们很难发现最优解会有什么性质。但是蓝色棋只有 $m$ 种走法，$m$ 为叶子结点数，如果我们能快速的求出每种走法最多放几个红色棋，这题就优雅的解决了。

这里先放个可以辅助思考的样例

输入 #1

13
1 2 3 4 5 2 7 1 9 10 11 1

输出 #1

3

因为是按照 $dfs$ 序给的所以可能会有点强度不足

继续看

既然我们统筹的钦定了每一种走法的结果,那显然是一种dp了

我们定义 $dp[u]$ 表示到达节点 $u$ 时最多的红色棋数量

从简到难: 叶子节点的转移方式很简单，显然有：

因为当蓝棋到达叶子时游戏直接结束，红棋已经没有跟上来增加贡献的机会了

考虑非叶子节点： 如果你手玩了会样例就会发现深度每加一，$dp$ 值最多加一，因为红蓝两色棋每一轮结束后都在相同深度（叶子节点除外但是我们已经处理过了）

而+1这一行为的必要条件是同一层有叶子节点（红棋能复制）

如果你这么写就会发现大样例的结果愉快的20->27

最终思路

我们会发现问题就在这个必要条件。

处理到某个节点时，不能只考虑同层是否有叶子，还要看这个叶子红棋能不能走的到

回到我们最初是怎么设计这个 dp 的，我们是把每条路径都作为主路径考虑了对吧，那么我们在最开始的时候，每个叶子都可以贡献答案。

但是当一个叶子贡献了答案之后，红棋就会被吸附回主路径上与这个叶子同一深度的点 $u$，所以此时就只有以 $u$ 为根节点的子树中的叶子节点可以贡献答案，除了这个子树的其他节点会被无效化

那我们贪心的考虑，对于每一个从根节点开始到达一个叶子节点的主路径 ，遍历到上面的一个非叶子节点，如果同层有可以抵达的叶子，直接加贡献，同时在这以后只考虑这个节点子树中的叶子

实现

定义 $pre[u]$ 表示 现在能对 $u$ 造成贡献的叶子所在的子树的根节点

正常 $pre[u]=pre[fa[u]]$ ，若出现红棋向主路径吸附，则 $pre[u]=u$

对于能否增加贡献需要实现 $query(u,k)$ 表示加测以 $u$ 为根的子树中是否存在深度为 $k$ 的叶子，具体的，调用 $query(pre[u],dep[u])$ 即可

正确性

这个看见能贡献就贴上去的贪心看起来不太正确的样子

具体来讲就是会不会出现我在这层不把红棋抓回来，后几层反而能造成更多贡献

下面感性证明一下（数学佬震怒）：

• 对于每一条主路径，在深度浅的点加贡献（吸附）无效化的点集 $A$ 真包含于 深度深的点加贡献后无效化的点集 $B$ .(或者是说若 $u$ 在 $v$ 的子树当中，以 $v$ 为根的子树的补集真包含于 以 $u$ 为根的的子树的补集)

所以越早吸附更新贡献对于后面的节点来说无效化的点集越小，且这个集合存在单调性，造成贡献的数量越多。

综上，该贪心正确性证毕（描述不太清楚，但至少正确）

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+17;
struct node{
	int nxt,to;
}q[N*2];int head[N],cnt;
void add(int x,int y){
	q[++cnt]=node{head[x],y};
	head[x]=cnt;
}
int n,f[N];
int dep[N],sum[N];//sum[i] = 深度为 i 的这一层的叶子结点数；
int isl[N];//是否是叶子 
vector <int> lef[N];//记录每一子树的叶深 
int pre[N];//记录上一次更新的点 
void dfs(int x,int fa){
	dep[x]=dep[fa]+1;
	f[x]=fa;
	bool ff=1;
	for(int i=head[x];i;i=q[i].nxt){
		int dd=q[i].to;
		if(dd==fa) continue;
		ff=0;
		dfs(dd,x);
		lef[x].insert(lef[x].end(),lef[dd].begin(),lef[dd].end());//对每个节点维护一个vec存它子树中叶子节点的深度 
	}
	if(ff){
		sum[dep[x]]++;
		isl[x]=1;
		lef[x].push_back(dep[x]);
	}else{
		sort(lef[x].begin(),lef[x].end());
	}
} 
bool query(int u,int k){
    auto& tmp=lef[u];
    return binary_search(tmp.begin(),tmp.end(),k);
}
int tot;
int dp[N];
void ddp(int x,int fa){
	for(int i=head[x];i;i=q[i].nxt){
		int dd=q[i].to;
		if(dd==fa) continue;
		pre[dd]=pre[x];//更新pre 
		if(isl[dd]) dp[dd]=dp[x];//这个点就是叶子 
		else {
			if(sum[dep[dd]]==0) dp[dd]=dp[x];//这层没叶子 
			else{
				int ff=0;
				if(query(pre[dd],dep[dd])){
					ff=1;
					pre[dd]=dd; 
				}
				if(ff==0) dp[dd]=dp[x];
				else dp[dd]=dp[x]+1;
			}
		}
		ddp(dd,x);
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	cin >> n;
	for(int i=2;i<=n;i++){
		int fa;
		cin>>fa;
		add(fa,i),add(i,fa);
	}
	dfs(1,0);
	dp[1]=1;
	pre[1]=1; 
	ddp(1,0);
	int res=0;
	for(int i=1;i<=n;i++){
		res=max(res,dp[i]);
	}
	cout << res;
	return 0;
} 
/*
13
1 2 3 4 5 2 7 1 9 10 11 1
*/

写一个有点丑陋的做法

首先我们考虑有一个很 $navie$ 的贪心，$lzd$ 已经说过了，不再赘述

然后我们直接考虑怎么做

我们直接设 $f_i$ 表示我当前有一红一蓝在 $i$ 点上

然后我们考虑转移

我们发现我们一定是从我子树下面某一个固定深度的点转移

然后我们只要快速找到这棵子树下面的某一深度的所有点就好了

然后我们可以用 $dfn$ 序来做这件事情

然后就秒了

CODE

#include<bits/stdc++.h>
using namespace std;
bool lf[200005];
vector<int>G[200005];
vector<int>ids[200005];
int dep[200005],dfn[200005],redfn[200005],siz[200005];
int mn[200005];
void dfs(int x){
	mn[x]=100000000;
	siz[x]=1;
	dfn[x]=++dfn[0];
	ids[dep[x]].push_back(dfn[x]);
	redfn[dfn[0]]=x;
	if(lf[x])mn[x]=dep[x];
	for(int i=0; i<(int)G[x].size(); i++){
		int y=G[x][i];
		dep[y]=dep[x]+1;
		dfs(y);
		mn[x]=min(mn[x],mn[y]);
		siz[x]+=siz[y];
	}
}
int f[200005];
void dfs2(int x){
	if(mn[x]==dep[x]){
//		f[x]=1;
		return;
	}
	int be=lower_bound(ids[mn[x]].begin(),ids[mn[x]].end(),dfn[x])-ids[mn[x]].begin();
	for(int i=be; i<(int)ids[mn[x]].size(); i++){
		int dn=ids[mn[x]][i];
		if(dn>dfn[x]+siz[x]-1){break;}
		dfs2(redfn[dn]);
		f[x]=max(f[x],f[redfn[dn]]);
	}f[x]++;
}
int main(){
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	int n,p;scanf("%d",&n);
	memset(lf,1,sizeof lf);
	for(int i=2; i<=n; i++){
		scanf("%d",&p);G[p].push_back(i);
		lf[p]=0;
	}dfs(1),dfs2(1);
	cout<<f[1];
	return 0;
}