传送门
给出一棵树，现在需要给树涂上 k k k种颜色，然后两种颜色之间的边作为这个颜色的边集，问 k k k种颜色的边集的交集最大是多少
如果去纠结如何涂点才能找到最多的边，这样很难想。实际上这种树的边和点都有的问题，不妨由点考虑边，或者由边考虑点。对于一条边，若其能作为最后的交集，那么它两侧的节点个数一定均大于等于 k k k，不妨举几个例子手玩一下。那么问题就变成了只要考虑每条边。
一开始我以为要遍历所有的边的两侧，这样的复杂度是 O ( n 2 ) O(n^2) O(n2)，但是实际上有个很巧妙的方法，我们随便找一个节点作为根，在统计每条边时，只需要看哪个是儿子节点，那么它的子树的节点个数一定都统计了，另外一边只需要 n − d [ v ] n-d[v] n−d[v]就能得到节点个数。
// // Created by Happig on 2020/10/6 // #include <bits/stdc++.h> #include <unordered_map> #include <unordered_set> using namespace std; #define fi first #define se second #define pb push_back #define ins insert #define Vector Point #define ENDL "\n" #define lowbit(x) (x&(-x)) #define mkp(x, y) make_pair(x,y) #define mem(a, x) memset(a,x,sizeof a); typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<double, double> pdd; const double eps = 1e-8; const double pi = acos(-1.0); const int inf = 0x3f3f3f3f; const double dinf = 1e300; const ll INF = 1e18; const int Mod = 1e9 + 7; const int maxn = 2e5 + 10; vector<int> G[maxn]; int d[maxn], f[maxn]; vector<pii> edges; inline int dfs(int u, int fa) { d[u] = 1, f[u] = fa; for (auto v: G[u]) { if (v != fa) d[u] += dfs(v, u); } return d[u]; } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t, n, k; cin >> t; while (t--) { cin >> n >> k; for (int i = 1; i <= n; i++) G[i].clear(); edges.clear(); for (int i = 1, u, v; i < n; i++) { cin >> u >> v; edges.push_back({u, v}); G[u].push_back(v), G[v].push_back(u); } dfs(1, -1); int ans = 0; for (auto pr: edges) { int u = pr.first, v = pr.second; if (f[u] == v) { int t1 = d[u], t2 = n - d[u]; if (t1 >= k && t2 >= k) ans++; } else if (f[v] == u) { int t1 = d[v], t2 = n - d[v]; if (t1 >= k && t2 >= k) ans++; } } cout << ans << ENDL; } return 0; }