【CQOI2017】小Q的棋盘（贪心）

题意：给你一棵 \(n\) 个点的树，从根节点开始走 \(m\) 步，最多能遍历多少个节点。

题解：

考虑我们走的路径，设起点是 \(S\)，终点是 \(T\)，那么我们肯定是走的类似这么一条路径：

设 \(S\to T\) 这条链的长为 \(l\)，那么我们在子树中走了 \(m-l\) 步，子树中恰好会走 \(\frac{m-l}{2}\) 个点，那么我们总共会走 \(l+1+\frac{m-l}{2}\) 个点。

那么我们挑 \(S\to T\) 最长的那条链作为 \(l\) 肯定是最优的，即最长链。

#include<bits/stdc++.h>

#define N 110

using namespace std;

inline 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<<1)+(x<<3)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}

int n,m;
int cnt,head[N],to[N<<1],nxt[N<<1];

void adde(int u,int v)
{
	to[++cnt]=v;
	nxt[cnt]=head[u];
	head[u]=cnt;
}

int dfs(int u,int fa)
{
	int maxn=0;
	for(int i=head[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v==fa) continue;
		maxn=max(maxn,dfs(v,u)+1);
	}
	return maxn;
}

int main()
{
	n=read(),m=read();
	for(int i=1;i<n;i++)
	{
		int u=read()+1,v=read()+1;
		adde(u,v),adde(v,u);
	}
	int l=dfs(1,0);
	if(m<=l) printf("%d\n",m+1);
	else printf("%d\n",min(n,l+1+(m-l)/2));
	return 0;
}

原文地址：http://www.cnblogs.com/ez-lcw/p/16837417.html