超棒的贪心构造题。
可以观察到每次操作的两个叶子，充要条件是路径上匹配边和非匹配边交替出现，操作完后全部取反。
首先考虑答案上界，从是否能取到上界入手，是本题的突破口。考虑操作两个叶子 \(x,y\)，收益为 \(dep[x] + dep[y] - 2dep[\text{LCA}(x, y)]\)。若固定根 \(r\)，当 \(\text{LCA}(x, y)\) 始终为 \(r\) 时取到上界。
当然 \(r\) 是不确定的，对于不同的 \(r\) 我们所述的上界会不同。有个 trick，节点两两匹配时，取 \(r\) 为重心时可以保证每次选的点都一定在 \(r\) 的不同子树中，这样 LCA 有了保证。
但是在题目限制下一定对吗？考虑目前 \(r\) 所匹配的点 \(x\)，那么我们选的其中一个点一定在 \(x\) 子树中。贪心选择，我们选择另一棵子树大小最大的子树，两棵子树各选择一个叶子操作。
不难发现，一棵子树中一定可以选出一个合法的叶子。
大力发挥人类智慧，我们对一棵子树进行 DFS，每次优先遍历非匹配边，得到的 DFS 序倒过来就是合法的操作顺序。
时间复杂度 \(O(n\log n)\)。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pir pair <ll, ll>
#define mkp make_pair
#define fi first
#define se second
#define pb push_back
using namespace std;
const ll maxn = 3e5 + 10, mod = 998244353;
ll n, rt, bs = 1e18, siz[maxn];
vector <ll> to[maxn];
void dfs1(ll u, ll fa = 0) {
ll mx = 0; siz[u] = 1;
for(ll v: to[u])
if(v ^ fa) {
dfs1(v, u), mx = max(mx, siz[v]);
siz[u] += siz[v];
} mx = max(mx, n - siz[u]);
if(mx < bs)
bs = mx, rt = u;
}
vector <ll> vec[maxn]; ll m, pos;
void dfs2(ll u, ll fa, ll id) {
siz[u] = 1, vec[id].pb(u);
ll mch = u & 1? u + 1 : u - 1;
for(ll v: to[u])
if(v != fa && v != mch) {
dfs2(v, u, id); siz[u] += siz[v];
}
if(mch ^ fa) dfs2(mch, u, id);
} set <pir> st;
ll Get(ll i) {
ll t = vec[i][vec[i].size() - 1];
vec[i].pop_back(); return t;
}
int main() {
scanf("%lld", &n);
for(ll i = 1; i < n; i++) {
ll u, v; scanf("%lld%lld", &u, &v);
to[u].pb(v), to[v].pb(u);
} dfs1(1);
for(ll v: to[rt]) {
dfs2(v, rt, ++m);
ll mch = rt & 1? rt + 1 : rt - 1;
if(v == mch) pos = m;
else st.insert(mkp((ll) vec[m].size(), m));
}
for(ll i = 1; i < n / 2; i++) {
pir tmp = *st.rbegin(); st.erase(tmp);
printf("%lld %lld\n", Get(pos), Get(tmp.se));
st.insert(mkp((ll) vec[pos].size(), pos));
pos = tmp.se;
}
printf("%lld %lld\n", rt, Get(pos));
return 0;
}