目录
显示
题目链接
https://www.luogu.com.cn/problem/P3698
题解
贪心地先往最深的节点走。
如果步数还有剩余呢?考虑用这些剩余的步数遍历其他子树。
一个显然的事实是,我们每多剩余两步,就可以多遍历一个点(别忘了遍历一个 \(n\) 个节点的子树需要走 \(2 \times (n-1)\) 条边)。
#include <cstdio> #include <algorithm> using namespace std; struct edge { int v,next; }e[205]; int head[105],dep[105],maxd,cnt; void addedge(int u,int v) { e[++cnt].v=v; e[cnt].next=head[u]; head[u]=cnt; } void dfs(int u,int fa) { dep[u]=dep[fa]+1; maxd=max(maxd,dep[u]); for(int i=head[u];i;i=e[i].next) if(e[i].v!=fa)dfs(e[i].v,u); } int main() { int v,n; scanf("%d%d",&v,&n); for(int i=1;i<v;i++) { int x,y; scanf("%d%d",&x,&y); addedge(x,y); addedge(y,x); } dep[0]=-1; dfs(0,0); if(maxd>=n)printf("%d\n",n+1); else printf("%d\n",min(v,maxd+1+(n-maxd)/2)); return 0; }