题解
根据题意,不回头是最好的(显然法)
\(dfs\)找到最长链,设长度为\(\mathrm{L}\),然后分类讨论:
如果\(\mathrm{L} > m\),答案就是\(m + 1\)
否则显然可以多走\(m-\mathrm{L} + 1\)步,可以多访问\((m-\mathrm{L} + 1) / 2\)步,于是答案就是
\(min\{n, \mathrm{L} + (m-\mathrm{L} + 1) / 2\}\)
证明???这一辈子都不可能的
代码
#include#include #include #include #define RG register#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)#define clear(x, y) memset(x, y, sizeof(x))inline int read(){ int data = 0, w = 1; char ch = getchar(); while(ch != '-' && (!isdigit(ch))) ch = getchar(); if(ch == '-') w = -1, ch = getchar(); while(isdigit(ch)) data = data * 10 + (ch ^ 48), ch = getchar(); return data * w;}const int N(110);struct edge { int next, to; } e[N << 1];int head[N], e_num, n, m, maxdep, vis[N];inline void add_edge(int from, int to){ e[++e_num] = (edge) {head[from], to}; head[from] = e_num;}void dfs(int x, int dep){ maxdep = std::max(maxdep, dep), vis[x] = 1; for(RG int i = head[x]; i; i = e[i].next) { int to = e[i].to; if(vis[to]) continue; dfs(to, dep + 1); }}int main(){#ifndef ONLINE_JUDGE file(cpp);#endif n = read(), m = read(); for(RG int i = 1, a, b; i < n; i++) a = read(), b = read(), add_edge(a, b), add_edge(b, a); dfs(0, 1); if(m < maxdep) printf("%d\n", m + 1); else printf("%d\n", std::min(n, maxdep + (m - maxdep + 1) / 2)); return 0;}