codeforces 1065F Up and Down the Tree

题目链接：codeforces 1065F Up and Down the Tree

题意：给出一棵树的节点数(n)以及一次移动的最大距离(k)，现在有一个标记在根节点1处，每一次可以进行一下的两个操作之一：

1、将标记移动至当前节点的子树中的某一个叶子

2、将当前标记向上移，向上移的距离不得超过(k)

求最多可以访问到多少个叶子结点

分析：一看就知道应该用树形dp去维护它

我们记(dp[u])表示以(u)为根节点的子树中最多可以访问多少个叶子结点

(dp[u])由两部分组成：一是跳到下面的节点再跳回(u)的叶子结点个数，二是跳到(u)的某一棵子树中不再跳回(u)时可以访问到的叶子结点个数

为了维护这个我们再记两个辅助数组(dis[u])表示距离(u)最近的叶子结点的距离，(back[u])表示在(u)的子树中跳到(u)再跳回来(u)时可以访问到的叶子结点个数

那么这两个数组的维护是显而易见的

对于(dp)数组的维护，第一部分就是(back[u])，直接加上即可

对于第二部分，我们要考虑的是(u)应该往哪一棵子树跳，由于能跳回来的已经在1中计算过了，我们在这里也就不能考虑这一部分，因此是选取最大的(dp[v]-back[v])去跳

最后注意在(dis[u]geq k)时，由于此时的(back[u])已经对它的父亲节点不会再存在贡献，直接清零即可

#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
const int maxd=1e9+7; 
struct node{
	int to,nxt;
}sq[2001000];
int n,k,head[1001000],all=0,dp[1001000],dis[1001000],back[1001000];

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 add(int u,int v)
{
	all++;sq[all].to=v;sq[all].nxt=head[u];head[u]=all;
}

void dfs(int u,int fa)
{
	dis[u]=maxd;int i;
	for (i=head[u];i;i=sq[i].nxt)
	{
		int v=sq[i].to;
		if (v==fa) continue;
		dfs(v,u);
		dis[u]=min(dis[u],dis[v]+1);
		back[u]+=back[v];
		dp[u]=max(dp[u],dp[v]-back[v]);
	}
	dp[u]+=back[u];
	if (dis[u]==maxd) {dis[u]=0;dp[u]=back[u]=1;}
	if (dis[u]>=k) back[u]=0;
}

int main()
{
	n=read();k=read();
	int i;
	for (i=2;i<=n;i++)
	{
	    int v=read();add(i,v);add(v,i);
	}
	memset(dp,0,sizeof(dp));
	memset(dis,0,sizeof(dis));
	memset(back,0,sizeof(back));
	dfs(1,0);
	printf("%d",dp[1]);
	return 0;
}