Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- int n;
- vector<int> g[100000];
- int par[100000][20];
- int tin[100000];
- int tout[100000];
- bool used[100000];
- int t = 0;
- void dfs(int v, int p) {
- tin[v] = t++;
- par[v][0] = p;
- for (int i = 1; i < 20; i++) {
- par[v][i] = par[par[v][i - 1]][i - 1];
- }
- for (int to : g[v]) {
- if (to == p) continue;
- dfs(to, v);
- }
- tout[v] = t++;
- }
- bool upper(int v1, int v2) {
- if (v1 == -1) return 1;
- else if (v2 == -1) return 0;
- return tin[v1] <= tin[v2] && tout[v1] >= tout[v2];
- }
- int lca(int v1, int v2) {
- if (upper(v1, v2)) return v1;
- if (upper(v2, v1)) return v2;
- for (int i = 19; i >= 0; i--) {
- if (!upper(par[v1][i], v2)) v1 = par[v1][i];
- }
- return par[v1][0];
- }
- vector<int> ans;
- vector<int> add[100000];
- bool done[100000];
- int l[100000];
- vector<int> st;
- int up = -1;
- void dfs2(int v, int p) {
- for (int to : g[v]) {
- if (to == p) continue;
- dfs2(to, v);
- }
- for (int x : add[v]) {
- if (!used[x]) {
- st.push_back(x);
- if (up == 0) {
- up = l[x];
- } else {
- if (upper(up, l[x])) {
- up = l[x];
- }
- }
- }
- }
- if (v == up) {
- for (int x : st) {
- used[x] = 1;
- }
- up = -1;
- st.clear();
- ans.push_back(v);
- }
- }
- int main() {
- ios_base::sync_with_stdio(0);
- for (int i = 0; i < 100000; i++) {
- done[i] = 0;
- }
- cin >> n;
- for (int i = 1; i < n; i++) {
- int v, to;
- cin >> v >> to;
- v--;
- to--;
- g[v].push_back(to);
- g[to].push_back(v);
- }
- dfs(0, 0);
- int m;
- cin >> m;
- for (int i = 0; i < m; i++) {
- int v1, v2;
- cin >> v1 >> v2;
- v1--;
- v2--;
- int v = lca(v1, v2);
- add[v1].push_back(i);
- add[v2].push_back(i);
- l[i] = v;
- }
- dfs2(0, -1);
- cout << ans.size() << "\n";
- for (int x : ans) {
- cout << x + 1 << " ";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement