这题大厉害了かふ。

· · 题解

题意简述：

给定一棵 n 个点的树，初始每个点上有一只青蛙，每只青蛙一开始都是绿色的。

一只青蛙可以跳跃一次到与其所在点相邻的点并改变颜色，若是绿色青蛙则变成棕色，反之变成绿色。一只青蛙最多跳跃 d 次。

如果两只在同一个点的青蛙颜色不同则可以组成一对合唱队，每只青蛙最多加入一对合唱队。

现在请求出能组成的最大合唱队数以及每一对是哪两只青蛙组成的。

定义 D(u,v) 为 u 和 v 两点间的距离。显然只有两点深度差为奇数时两点上的青蛙跳到一起才能满足限制。

所有点上初始都有一只青蛙，我们有贪心：若某两点 u,v 上的青蛙可以以 <d 的跳跃次数跳到一起，则将两点的 LCA 向上提一定不劣。

证明形如，LCA 向上提后 D(u,v) 增加 2 奇偶性不变，同时原来保证 D(u,v) 为奇数且 <d 则有 D(u,v) \leq d-2。

将点按深度奇偶分组，两组之间的深度差显然为奇数，两集合做启发式合并得到一个 \mathcal{O}(nd\log n) 的做法。

用将子节点集合并入当前点集合的实现太不优美了！考虑更换实现，把 DSU 替换成轻重儿子的处理形式。去掉维护奇偶的集合，用 \max \{\text{dep}_i\} 个全局集合维护每个深度的节点信息。

建立一个从深度和奇偶性到节点的映射，当一个深度为 \text{dep}_v 的子节点合并至当前深度 \text{dep}_u 的节点 u 时，我们精细查找里面满足 \text{dep}_v+\text{dep}_{v'}-2\text{dep}_u\le d 且最大的 \text{dep}_{v'}，需要保证奇偶性所以映射分了奇偶。当这两个点可以达到可合并的最大距离 d 时应在深度为 \dfrac{\text{dep}_v+\text{dep}_{v'}-d}{2} 时相遇。把这个深度挂在一个东西上等算到这个深度的时候更新。

但是你显然不能每次遍历一遍所有待更新深度，利用从下往上合并这个性质，把所有深度塞进一个堆里，深度较大的在前，满足堆顶和当前深度相同时合并，否则继续向上计算。

到根了当然不能继续计算，把所有节点取出来处理。

实现好难……

#include <bits/stdc++.h>
#define break ({break;})
#define continue ({continue;})
#define return(kafu) ({return kafu;})

using namespace std;
typedef long long i64;
typedef double f16;
typedef pair <int, int> pii;

const int N = 5e5 + 10;
int n, d, dep[N], siz[N], hev[N], dfn[N], dcnt, d2i[N];
unordered_map <int, bool> exc[N]; // 某个深度的点要匹配点的期望深度标记 (?)
map <int, vector <int> > ind[2];
vector <int> g[N];
vector <pii> ans;
bool used[N];

struct vertex { int d, i; vertex (int _d, int _i) : d (_d), i (_i) {} };
struct cmp_vertex { bool operator () (vertex x, vertex y) { return x.d < y.d; } };
priority_queue <vertex, vector <vertex>, cmp_vertex> vt;
#define qry_b(v,w,p) auto v = w.upper_bound (p)
int oe (int c) { return (c & 1); }

void DFS (int u, int f)
{
    dep[u] = dep[f] + 1, siz[u] = 1;
    for (int v : g[u])
    {
        if (v == f) continue;
        DFS (v, u), siz[u] += siz[v];
        if (siz[v] > siz[hev[u]]) hev[u] = v;
    }
}

void reset (int u)
{
    for (int i = dfn[u]; i <= dfn[u] + siz[u] - 1; i ++)
        exc[dep[d2i[i]]].clear ();
    ind[0].clear (), ind[1].clear ();
    while (vt.size ()) vt.pop ();
}

void find (int u, int c, int ad = -1) // 在 u 的子树里给一个深度为 c 的点找到匹配点 (?)
{
    qry_b (v, ind[!oe (c)], dep[u] * 2 + d - c);
    if (v != ind[!oe (c)].begin ())
    {
        v --; int dv = v -> first;
        if (!exc[c].count (dv)) vt.emplace ((c + dv - d) / 2, c), exc[c][dv] = true;
    }
    if (~ad) ind[oe (c)][c].push_back (ad);
}

void process (int u)
{
    while (vt.size ())
    {
        if (vt.top ().d < dep[u] && u != 1) return; // 堆顶不足 dep 且不为根返回
        int ed = vt.top ().i, od = vt.top ().d * 2 + d - ed; vt.pop ();
        exc[ed].erase (od); if (ed & 1) swap (ed, od); // 分奇偶
        if (!ind[0].count (ed) || !ind[1].count (od)) continue;

        int e = ind[0][ed].back (), o = ind[1][od].back (); // 取出对应点
        ind[0][ed].pop_back (), ind[1][od].pop_back ();
        if (ind[0][ed].empty ()) ind[0].erase (ed); // 为空时删除该深度
        if (ind[1][od].empty ()) ind[1].erase (od);
        ans.emplace_back (e, o), used[e] = used[o] = true;

        qry_b (en, ind[0], ed); qry_b (on, ind[1], od);
        if (en != ind[0].begin ()) en --, find (u, en -> first);
        if (on != ind[1].begin ()) on --, find (u, on -> first);
    }
}

void DSU (int u, int f)
{
    dfn[u] = ++ dcnt, d2i[dcnt] = u;
    for (int v : g[u])
        if (v != f && v != hev[u]) DSU (v, u), reset (v);
    if (hev[u]) DSU (hev[u], u);
    find (u, dep[u], u);
    for (int v : g[u])
        if (v != f && v != hev[u])
            for (int i = dfn[v]; i <= dfn[v] + siz[v] - 1; i ++)
                if (!used[d2i[i]]) find (u, dep[d2i[i]], d2i[i]);
    process (u);
}

int main ()
{
    cin >> n >> d;
    for (int i = 1, u, v; i < n; i ++)
        cin >> u >> v, g[u].push_back (v), g[v].push_back (u);
    DFS (1, 0), DSU (1, 0), cout << ans.size () << '\n';
    for (pii i : ans) cout << i.first << ' ' << i.second << '\n';
    return 0;
}