F. 小紫的树上染色
任意指定一个根节点，先深搜到叶子结点，然后退上来的时候加上子树贡献，一旦到二分 mid，需要染紫的节点数就加1，最后和 k 比一下，看能不能在 k 个紫色内符合 mid
对于每一个父节点再算儿子的贡献时，一定要等所有儿子贡献全部加上再判，否则就会有子树因为提前 return 而遍历不到。
遍历树不需要 vis 数组，带上 fa 不能回退就可以了。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5, INF = 1e18;int T, n, k, cnt, ans;
vector<int> G[N];int dfs(int u, int fa, int mid)
{int res = 0;for (auto v : G[u]){ if (v != fa)res += dfs(v, u, mid);}if (res + 1 > mid){cnt ++;return 0;}return res + 1;
}bool check(int mid)
{cnt = 0;int a = dfs(1, 0, mid);return cnt <= k;
}signed main()
{cin >> n >> k;for (int i = 1; i < n; i ++){int u, v;cin >> u >> v;G[u].push_back(v), G[v].push_back(u);}int l = -1, r = n + 1, mid;while (l + 1 < r){mid = l + (r - l) / 2;if (check(mid))r = mid;elsel = mid;}cout << r;return 0;
}
