Submission #1369502

#TimeUsernameProblemLanguageResultExecution timeMemory
1369502gohchingjaykNetwork (NOI23_network)C++20
100 / 100
286 ms65984 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll

using ii = pair<int, int>;
using iii = pair<ii, int>;
#pragma GCC optimize("O3")

constexpr int MAXN = 200'000 + 5;
constexpr int INF = 1e18 + 5;
constexpr int LOG = 20;

int cntr = -1;
vector<int> adjlist[MAXN];
int pa[LOG][MAXN];
int pre[MAXN];
int post[MAXN];
int depth[MAXN];
int fenwick[MAXN];

void upd(int x) {
	int l = pre[x];
	int r = post[x];
	l += 1, r += 1;
	
	auto point_update = [&](int p, int v) {
		for (; p <= MAXN; p += (p & -p)) fenwick[p] += v;
	};
	
	point_update(l, 1);
	point_update(r+1, -1);
}

bool rq(int x) {
	x = pre[x];
	x += 1;
	
	int tot = 0;
	for (; x > 0; x &= x-1) {
		tot += fenwick[x];
	}
	
	return tot > 0;
}

void dfs(int x) {
	pre[x] = ++cntr;
	
	for (int ch : adjlist[x]) {
		if (ch == pa[0][x]) continue;
		pa[0][ch] = x;
		depth[ch] = depth[x] + 1;
		for (int i = 1; i < LOG; ++i) pa[i][ch] = pa[i-1][pa[i-1][ch]];
		dfs(ch);
	}
	
	post[x] = cntr;
}

int lca(int a, int b) {
	// WLOG depth[a] <= depth[b]
	if (depth[a] > depth[b]) swap(a, b);
	
	int diff = depth[b] - depth[a];
	for (int i = LOG-1; i >= 0; --i) {
		if ((diff >> i) & 1) b = pa[i][b];
	}
	
	if (a == b) return a;
	
	for (int i = LOG-1; i >= 0; --i) {
		if (pa[i][a] != pa[i][b]) {
			a = pa[i][a], b = pa[i][b];
		}
	}
	
	return pa[0][a];
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

	for (int i = 0; i < LOG; ++i) pa[i][1] = 1;
	depth[1] = 0;

	int N, M; cin >> N >> M;
	for (int i = 0; i < N-1; ++i) {
		int u, v; cin >> u >> v;
		adjlist[u].emplace_back(v);
		adjlist[v].emplace_back(u);
	}

	dfs(1);
	
	vector<iii> paths(M);
	for (int i = 0; i < M; ++i) {
		int a, b; cin >> a >> b;
		int l = lca(a, b);
		paths[i] = iii{ii{a, b}, l};
	}
	
	sort(paths.begin(), paths.end(), [&](const iii &a, const iii &b) {
		return depth[a.second] > depth[b.second];
	});
	
	vector<int> rem;
	for (iii path : paths) {
		auto [u, v] = path.first;
		int l = path.second;
		if (rq(u) || rq(v)) continue;
		rem.emplace_back(l);
		upd(l);
	}
	
	cout << rem.size() << '\n';
	for (int i : rem) cout << i << ' ';
}

/*
9 4
1 2
2 3
2 6
3 4
4 5
4 7
6 9
7 8
6 2
5 3
4 8
5 9
*/
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...