题意:给你一棵 \(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;
}
标签:ch,frac,个点,int,while,CQOI2017,棋盘,贪心
From: https://www.cnblogs.com/ez-lcw/p/16837417.html