题解 | #小红开灯（一）#

贴一个贪心做法，不知道对不对(不会用dp解决), 从底层结点往上找，如果它的状态是开灯的话，那么它最优解肯定是它的父节点以及父节点的父节点，否则就是它本身和父节点(如果父节点状态是开灯的情况下)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pi = pair<ll, ll>;
using ld = long double;
const int N = 1e6+ 10;
int mod = 1e9 + 7;
ll n,m;
ll a[N];
vector<int> g[N];
int fa[N];
vector<int> ceng[N];
int mx = 0;
void dfs(int cur, int faa, int c) {
    ceng[c].push_back(cur);
    fa[cur] = faa;
    mx = max(mx, c);
    for(auto i: g[cur]) {
        if(i == faa) continue;
        dfs(i, cur, c + 1);
    }
}
void solve()
{
    cin >> n;
    for(int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, -1, 0);
    vector<pi> t;
    vector<bool> v(n+5, 0);
    for(int i = mx; i >= 0; i--) {
        for(auto j: ceng[i]) {
            if(v[j]) continue;
            int FA = fa[j];
            if(FA == -1 || v[FA]) continue;
            int FFA = fa[FA];
            if(FFA == -1 || v[FFA]) {
                t.push_back({j, FA});
                v[j] = 1;
                v[FA] = 1;
            } 
            else {
                t.push_back({FFA, FA});
                v[FFA] = 1;
                v[FA] = 1;
            }
        }
    }
    cout << t.size() << '\n';
    for(auto i: t) {
        cout << i.first << ' ' << i.second << '\n';
    }
}
int main()
{
  // 请在此输入您的代码
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
//     cin >> _;
    while(_--) solve();
}