在天狼星物理技术学院，你不仅能看到普通的青蛙，还能遇见会变色的树蛙！这些神奇的小家伙可以从绿色变成棕色，或者从棕色变回绿色，简直就像自然界的魔术师。
所谓树，是一个没有环的连通图。树上的每个节点都住着一只青蛙，初始时它们全是绿色的。青蛙们喜欢在树上跳来跳去，每次跳跃会从当前节点沿着边跳到旁边的节点。每跳一次，它们的颜色就会切换到相反的颜色。
青蛙们最爱成双成对地唱歌，但每一对必须由一只绿色和一只棕色的青蛙组成。为了组成一对，某只青蛙需要跳到另一只青蛙所在的节点，且跳跃次数不能超过 \(d\) 次。为了保证到达时颜色与对方不同，跳跃次数必须是奇数。
你的任务是找出最多能组成多少对青蛙合唱团。每只青蛙只能加入一对。如果能正确计算出最多的合唱团数量，你就能为子任务拿到部分分数。要想拿满分，你还得指出哪些青蛙应该配对，才能达到这个最大数量。
知识点：\(\textbf{DSU on Tree}\)，贪心。
\(\textbf{Subtask 1}\) : \(n \le 14\)
考虑暴力的挑选出点对，写一个checker看看是否合法。
复杂度 \(O(2^n)\)
\(\textbf{Subtask 2}\) : \(n ≤ 300000，d=n−1\)
真是更简单了，既然 \(d=n-1\)，说明全部都可以匹配。
那么我们直接通过奇偶层任意匹配就行了。
复杂度：\(O(n)\)
\(\textbf{Subtask 3,4,5,6,7,8}\)
在这里，我们需要深入思考了。
我们可以手玩一下样例，发现似乎有贪心。
这里引用 @Lucyna_Kushinada 的证明。
可以从下往上贪心，两个
set在节点 u 启发式合并时，所模拟的路径是从其中一个set里的节点走到 u，再走到另一个set里的节点，如果路程为 D 或者当前在根节点，那就贪心计入答案。
考虑这么贪心为什么是对的，一对点匹配的贡献都是相同的 1 是前提，而贪心是有顺序的从下往上，显然越晚（路程越靠近 D）配对越好，这说明 u 以下的节点不能让他们这样走的路程为 D，即使往上走还可能出现距离刚好为 D 的点，实际上还不如偏安一隅，往上走浪费的不仅是自己的机会，还有别的点的机会，下面也没有能和你配的了，还能怎么办不必多说。
复杂度 \(O(nd \log n)\)
注意到 \(d\) 是很小的。
可以通过，\(64 pts\)。
\(\huge \mathscr{Code}\)
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 100;
int n, d, siz[N], dep[N], hson[N], cnt[N], vis[N];
vector<int> g[N];
set<pair<int, int>> S[2];
vector<pair<int, int>> ans;
void dfsget(int u, int fath) {siz[u] = 1;dep[u] = dep[fath] + 1;for (int e : g[u]) {if (e == fath) continue;dfsget(e, u);siz[u] += siz[e];if (!hson[u] or siz[e] > siz[hson[u]]) hson[u] = e;}
}
void add(int u, int fath, int del) {if (!vis[u]) {S[dep[u] & 1].insert(make_pair(dep[u], u));}for (int e : g[u]) {if (e == fath or e == del) continue;add(e, u, del);}
}
void clear(int u, int fath) {if (!vis[u]) S[dep[u] & 1].erase(make_pair(dep[u], u));for (int e : g[u]) {if (e == fath) continue;clear(e, u);}
}
void calc(int rt) {vector<pair<int, int>> del;for (auto e : S[0]) {auto [depu, u] = e;if (depu > dep[rt] + d) {del.push_back(e);continue;}auto it = S[1].upper_bound(make_pair(d + 2 * dep[rt] - depu, N));if (it == S[1].begin()) continue;--it;auto [depv, v] = *it;if (rt != 1 && d + 2 * dep[rt] - depu != depv) continue;vis[u] = vis[v] = 1;S[1].erase(it);del.push_back(e);ans.push_back(make_pair(u, v));}for (auto e : del) S[0].erase(e);
}
void DSU(int u, int fath) {for (int e : g[u]) {if (e == fath or e == hson[u]) continue;DSU(e, u);clear(e, u);}if (hson[u]) DSU(hson[u], u);add(u, fath, hson[u]);calc(u);
}
int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> d;if (!(d & 1)) d--;for (int i = 1; i < n; i++) {int x, y;cin >> x >> y;g[x].push_back(y), g[y].push_back(x);}dfsget(1, 0);DSU(1, 0);cout << ans.size() << '\n';for (auto e : ans) cout << e.first << ' ' << e.second << '\n';return 0;
}
\(\textbf{Subtask all}\)
实际上，我们可以敏锐的发现，上面的代码是过不了 \(2\) 号点的，因为 \(d\) 太大了。
考虑我们的贪心，既然要在刚好等于 \(d\) 的时候匹配，每次收集子树信息是不是太浪费了。
假设现在有一个点 \(u\)，深度记作 \(dep_u\)。
找到最大的满足 \(d_u+d_v−2 \times d_{lca}≤d\) 且奇偶性与 \(d_u\) 相反的 \(d_v\)，计算出他们可以完美合并（路程刚好为 \(d\)）的时候的深度，然后等到此深度的时候再看能不能计入答案。
题解从略。
\(\huge \mathscr{Code}\)
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define push_back emplace_back
using namespace std;
const int N = 5e5 + 100;
int n, D, siz[N], dep[N], hson[N];
double anss;
vector<int> g[N];
vector<pair<int, int>> ans;
struct node {int lim = 0;map<int, vector<int>> s[2];priority_queue<pair<int, int>> q;void Clear() {s[0].clear(), s[1].clear();while (q.size()) q.pop();}void Update() {lim--;for (auto i : { 0,1 })while (s[i].size()) {auto it = (--s[i].end());if (it->first > lim + D) s[i].erase(it);else break;}}void Find(int d) {int z = (d & 1) ^ 1;auto it = s[z].upper_bound(D + 2 * lim - d);if (it == s[z].begin()) return;--it;int lim2 = (it->first + d - D) / 2;int tmpd = ((d & 1) ? it->first : d);q.push(make_pair(lim2, tmpd));}void Insert(int d, int x) {if (s[d & 1].find(d) != s[d & 1].end()) s[d & 1][d].push_back(x);else s[d & 1][d].push_back(x), Find(d);}void Match() {while (q.size()) {auto [fi, se] = q.top();if (lim > fi) break;q.pop();int d1 = se, d2 = D + 2 * lim - d1;if (s[0].find(d1) == s[0].end()) continue;if (s[1].find(d2) == s[1].end()) continue;int u = s[0][d1].back(), v = s[1][d2].back();s[0][d1].pop_back(), s[1][d2].pop_back();ans.push_back(make_pair(u, v));if (s[0][d1].empty()) s[0].erase(d1);if (s[1][d2].empty()) s[1].erase(d2);auto it = s[0].upper_bound(d1);if (it != s[0].begin()) { --it, Find(it->first); }it = s[1].upper_bound(d2);if (it != s[1].begin()) { --it, Find(it->first); }}}
}S[N];
void dfsget(int u, int fath) {siz[u] = 1;dep[u] = dep[fath] + 1;for (int e : g[u]) {if (e == fath) continue;dfsget(e, u);siz[u] += siz[e];if (!hson[u] or siz[e] > siz[hson[u]]) hson[u] = e;}
}
void DSU(int u, int fath) {if (!hson[u]) {S[u].lim = dep[u];S[u].Insert(dep[u], u);return;}DSU(hson[u], u);swap(S[u], S[hson[u]]);S[u].Update();S[u].Insert(dep[u], u);for (int e : g[u]) {if (e == fath or e == hson[u]) continue;DSU(e, u);for (int i : {0, 1}) {for (auto z : S[e].s[i]) for (int x : z.second) S[u].Insert(z.first, x);}S[e].Clear();}S[u].Match();
}
set<pair<int, int>> lastS[2];
int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> D;if (!(D & 1)) D--;for (int i = 1; i < n; i++) {int x, y;cin >> x >> y;g[x].push_back(y), g[y].push_back(x);}dfsget(1, 0);DSU(1, 0);for (int i : {0, 1}) {for (auto z : S[1].s[i]) for (int x : z.second) lastS[i].insert(make_pair(-dep[x], x));}for (auto z : lastS[0]) {auto [depu, u] = z;depu = -depu;auto it = lastS[1].lower_bound(make_pair(-D - 2 * dep[1] + depu, 0));if (it == lastS[1].end()) continue;auto [depv, v] = *it;depv = -depv;lastS[1].erase(it);ans.push_back(make_pair(u, v));}cout << ans.size() << '\n';for (auto e : ans) cout << e.first << ' ' << e.second << '\n';return 0;
}