#include "nachia-library/tree/heavylightdecomposition.hpp" #include #include #include #include using namespace std; using i64 = long long; using u64 = unsigned long long; using i32 = int; using u32 = unsigned int; #define rep(i,n) for(int i=0; i<(n); i++) struct LCAAuxiliary{ int n; nachia::HeavyLightDecomposition hld; LCAAuxiliary(const vector>& edges, int root = 0){ hld = nachia::HeavyLightDecomposition(edges); } pair, vector> query_once(vector vtxs){ sort(vtxs.begin(), vtxs.end(), [this](int l, int r)->bool{ return hld.to_seq(l) < hld.to_seq(r); }); vector res; vector parent; vector dfs; for(auto v : vtxs){ if(dfs.size()){ int g = hld.lca(res[dfs.back()], v); while(1 < dfs.size()){ int ci = dfs.back(); if(!(hld.depth(g) < hld.depth(res[ci]))) break; dfs.pop_back(); if(hld.depth(g) < hld.depth(res[dfs.back()])) parent[ci] = dfs.back(); else if(res[dfs.back()] == g){ parent[ci] = dfs.back(); break; } else{ parent[ci] = res.size(); break; } } if(hld.depth(g) < hld.depth(res[dfs.back()])){ parent[dfs.back()] = res.size(); dfs.pop_back(); } if(!dfs.size() || res[dfs.back()] != g){ dfs.push_back(res.size()); parent.push_back(-1); res.push_back(g); } } if(!res.size() || res.back() != v){ dfs.push_back(res.size()); parent.push_back(-1); res.push_back(v); } } while(dfs.size() > 1){ int vi = dfs.back(); dfs.pop_back(); parent[vi] = dfs.back(); } return make_pair(move(res), move(parent)); } }; int main() { int N; cin >> N; vector> E(N); rep(i,N-1){ int u,v; cin >> u >> v; E[u].push_back(v); E[v].push_back(u); } int V; cin >> V; vector A(V); rep(i,V) cin >> A[i]; auto [xV,xP] = LCAAuxiliary(E).query_once(A); vector ansV = xV; sort(ansV.begin(), ansV.end()); vector> ansE; for(int i=0; i v) swap(u,v); ansE.push_back({u,v}); } sort(ansE.begin(), ansE.end()); cout << ansV.size() << "\n"; rep(i,ansV.size()){ if(i) cout << " "; cout << ansV[i]; } cout << "\n"; for(auto [u,v] : ansE) cout << u << " " << v << "\n"; return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr); } } ios_do_not_sync_instance;

提出日時
ユーザー	Nachia
言語	C++ (GCC 9.3.0)
結果	CE
実行時間	ms
メモリ	kb

指定された頂点たちの最小共通祖先関係を保って木を圧縮してできる補助的な木

コンパイルエラー