agc001_c题解

水的炸天，不做解释自己看吧

#include<bits/stdc++.h>
#define MAXN 2010
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
namespace SHuxinn{struct node {int lst;int dep;int nxt ;} tree[MAXN * 4];int n , k , cnt , ans;int dfs(int x , int fa , int dis) {int ans = 0;for (int i = tree[x].lst ; i ; i = tree[i].nxt) {if (tree[i].dep != fa){ans += dfs(tree[i].dep , x , dis + 1);}}if(dis > k) return ans + 1;else return ans;}void Sx5() {cin >> n >> k;int u , v;for (int i = 1 ; i < n ; i ++) {cin >> u >> v;tree[++cnt].dep = u;tree[cnt].nxt = tree[v].lst;tree[v].lst = cnt;tree[++cnt].dep = v;tree[cnt].nxt = tree[u].lst;tree[u].lst = cnt;}ans = inf;if (k % 2 == 0) {k /= 2;for (int i = 1 ; i <= n ; i ++)ans = min(ans , dfs(i , 0 , 0));} else {k = (k - 1) / 2;for (int i = 1 ; i <= n ; i ++){for (int j = tree[i].lst ; j ; j = tree[j].nxt){if (i < tree[j].dep)ans = min(ans , dfs(i , tree[j].dep , 0) + dfs(tree[j].dep , i , 0));}}}cout << ans;return;}
}
signed main(){freopen("tree.in" , "r" , stdin);freopen("tree.out" , "w" , stdout);SHuxinn::Sx5();return 0;
}