2021 ICPC Southeastern Europe Regional Contest 树上dfs+思维

|–>传送门> n; for(int i = 1; i > v; g[u].emplace_back(v); g[v].emplace_back(u); deg[u]++, deg[v]++; } function getmin = [&](int u, int fa){ bool flag = true; w[u] = INF; for(auto nxt : g[u]){ if(nxt == fa) continue; flag = false; getmin(nxt, u); w[u] = min(w[u], w[nxt]); } if(flag) w[u] = u; }; function dfs = [&](int u, int fa, int dir){ vector sot; for(auto v : g[u]){ if(v == fa) continue; sot.emplace_back(mkp(w[v], v)); } if(!sot.size()) { ans.emplace_back(u); return; } sort(sot.begin(), sot.end()); if(dir == 0){ for(auto x : sot) dfs(x.sec, u, 0); ans.emplace_back(u); } else { for(int i = 0; i sot.back().fir) dfs(sot.back().sec, u, 0), ans.emplace_back(u); else ans.emplace_back(u), dfs(sot.back().sec, u, 1); } }; int st = 0; for(int i = n; i >= 1; --i) if(deg[i] == 1) st = i; getmin(st, 0); dfs(st, 0, 1); for(auto x : ans) cout