题目传送门(BZOJ)
>原文链接<

题解 :

先说贪心方法 :

我们处理出来一条最长的链的长度, 分三种情况讨论 :

若步数小于最长链, 只能走步数+1个点

若步数足够走完整棵树, 那就可以走N个点

否则, 按链上点只需要一步, 其他点需要两步来求得答案.

一个感性的证明, 看起来和实际上都很对 :

对于链上的点, 显然一步即可到达,

对于非链上的点, 如果走了它, 就要回到链上,

若它是链的儿子, 则来一步, 回去一步, 共两步

若它不是链的儿子, 那么它的父亲肯定在贡献里,

同时父亲的步数代价已经是两步了,

走到这个点对于父亲并不需要花更多的步数, 只需要从父亲来一步, 回去一步.

另外, 对于一定回到链上的解释是这样的, 若不回到链上, 相当于选择了一条更短的链,

又由于非链代价要比链上高, 一定不优.

代码 :

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define rev(i, p) for(Edge *i = h[p]; i; i = i->next)#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)char buf[100000], *p1, *p2; const int N = 100;inline int rd() { int x = 0; char ch = nc(); while(!isdigit(ch)) ch = nc(); while(isdigit(ch)) x = ((x+(x<<2))<<1)+(ch^48), ch = nc(); return x;}struct Edge { int to; Edge *next;}*h[N], e[N<<1];inline void addEdge(int u, int v) { static int _; Edge *tmp = &e[++_]; tmp->to = v; tmp->next = h[u]; h[u] = tmp;}int dep[N];void dfs(int p, int fa) { dep[p] = dep[fa]+1; rev(i, p) if(i->to != fa) { dfs(i->to, p); }}int main() { int n = rd(), s = rd(), len = 0; for(int i = 2; i <= n; i ++ ) { int u = rd(), v = rd(); addEdge(u, v), addEdge(v, u); } dfs(0, 0); for(int i = 0; i < n; i ++ ) { len = max(len, dep[i]-1); } if(s <= len) printf("%d\n", s+1); else if(s >= len+2*(n-len+1)) printf("%d\n", n); else printf("%d\n", len+(s-len)/2+1);}