verify/codeforces/codeforces-1074F.test.cpp

• View this file on GitHub
• Last update: 2022-07-21 16:12:33-04:00
• Problem: https://codeforces.com/contest/1074/problem/F

Depends on

• library/contest/template-minimal.hpp
• Sparse Table (library/data-structures/1d-range-queries/sparse-table.hpp)
• LCA RMQ (library/graphs/lca-rmq.hpp)

Code

#define PROBLEM "https://codeforces.com/contest/1074/problem/F"

#include "../../library/contest/template-minimal.hpp"
#include "../../library/graphs/lca-rmq.hpp"

template <class T> struct SegmentTree {
	using U = pair<T, int>;

	const U ID = make_pair(numeric_limits<T>::max(), 1);

	int sz;	
	
	vector<U> st; // min, cnt

	vector<T> lz; // lazy


	void init(int _sz) {
		sz = 1;
		while (sz < _sz) {
			sz <<= 1;
		}
		st.assign(2 * sz, make_pair(0, 1));
		lz.assign(2 * sz, 0);
		for (int i = sz - 1; i >= 1; --i) {
			pull(i);
		}
	}

	U comb(U x, U y) {
		U res;
		if (x.first < y.first) {
			res = x;
		} else if (x.first > y.first) {
			res = y;
		} else {
			res.first = x.first;
			res.second = x.second + y.second;
		}
		return res;
	}

	void pull(int i) {
		st[i] = comb(st[2 * i], st[2 * i + 1]);
	}

	void push(int i, int l, int r) {
		if (lz[i] == 0) {
			return;
		}
		st[i].first += lz[i];
		if (l != r) {
			for (int j = 0; j < 2; ++j) {
				lz[2 * i + j] += lz[i];
			}
		}
		lz[i] = 0;
	}

	void upd(int lo, int hi, T inc, int i = 1, int l = 0, int r = -1) {
		if (r == -1) {
			r += sz;
		}
		push(i, l, r);
		if (r < lo || hi < l) {

		} else if (lo <= l && r <= hi) {
			lz[i] = inc;
			push(i, l, r);
		} else {
			int m = (l + r) >> 1;
			upd(lo, hi, inc, 2 * i, l, m);
			upd(lo, hi, inc, 2 * i + 1, m + 1, r);
			pull(i);
		}
	}

	U query(int lo, int hi, int i = 1, int l = 0, int r = -1) {
		if (r == -1) {
			r += sz;
		}
		push(i, l, r);
		if (r < lo || hi < l) {
			return ID;
		} else if (lo <= l && r <= hi) {
			return st[i];
		} else {
			int m = (l + r) >> 1;
			return comb(query(lo, hi, 2 * i, l, m), query(lo, hi, 2 * i + 1, m + 1, r));
		}
	}

	int zeros(int lo, int hi) {
		auto res = query(lo, hi);
		if (res.first == 0) {
			return res.second;
		} else {
			return 0;
		}
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, q;
	cin >> n >> q;
	LCARMQ L;
	L.init(n);
	vector<vector<int>> g(n);
	for (int i = 0; i < n - 1; ++i) {
		int u, v;
		cin >> u >> v;
		--u, --v;
		g[u].push_back(v);
		g[v].push_back(u);
		L.ae(u, v);
	}	
	vector<int> in(n);
	vector<int> out(n);
	int ti = 0;
	function<void(int, int)> dfs = [&](int u, int p) {
		in[u] = ti++;
		for (int v : g[u]) {
			if (v != p) {
				dfs(v, u);
			}
		}
		out[u] = ti - 1;
	};
	dfs(0, -1);
	L.gen(0);
	set<pair<int, int>> used;
	SegmentTree<int> seg;
	seg.init(n);	
	while (q--) {
		int u, v;
		cin >> u >> v;
		--u, --v;
		if (u > v) {
			swap(u, v);
		}
		auto add = [&](int u, int v, int t) {
			int lca = L.lca(u, v);
			if (lca == v) {
				swap(u, v);
			}
			if (lca == u) {
				int child = L.get_child(u, v);
				seg.upd(in[child], out[child], t);
				seg.upd(in[v], out[v], -t);
			} else {
				seg.upd(0, n - 1, t);
				seg.upd(in[u], out[u], -t);
				seg.upd(in[v], out[v], -t);
			}
		};
		if (used.count(make_pair(u, v))) {
			used.erase(make_pair(u, v));
			add(u, v, -1);
		} else {
			used.emplace(u, v);
			add(u, v, 1);
		}
		cout << seg.zeros(0, n - 1) << '\n';
	}
	return 0;
}

#define PROBLEM "https://codeforces.com/contest/1074/problem/F"


#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;


template <class T> struct SparseTable {
	std::vector<T> v;
	std::vector<std::vector<int>> jump;

	int level(int x) { return 31 - __builtin_clz(x); }

	int comb(int a, int b) {
		return v[a] == v[b] ? std::min(a, b) : (v[a] < v[b] ? a : b);
	}

	void init(const std::vector<T>& _v) {
		v = _v;
		jump = {std::vector<int>((int)v.size())};
		iota(jump[0].begin(), jump[0].end(), 0);
		for (int j = 1; (1 << j) <= (int)v.size(); j++) {
			jump.push_back(std::vector<int>((int)v.size() - (1 << j) + 1));
			for (int i = 0; i < (int)jump[j].size(); i++) {
				jump[j][i] = comb(jump[j - 1][i], jump[j - 1][i + (1 << (j - 1))]);
			}
		}
	}

	int index(int l, int r) {
		assert(l <= r);
		int d = level(r - l + 1);
		return comb(jump[d][l], jump[d][r - (1 << d) + 1]);
	}

	T query(int l, int r) {
		return v[index(l, r)];
	}
};

struct LCARMQ {
	int n; 
	std::vector<std::vector<int>> adj;
	std::vector<int> dep, in, par, rev, out, pos;
	std::vector<std::pair<int, int>> tmp;
	SparseTable<std::pair<int, int>> S;
	std::vector<std::vector<int>> sparse;
	int ti = 0;

	void init(int _n) {
		n = _n;
		adj.resize(n);
		dep = in = out = par = rev = pos = std::vector<int>(n);
		sparse = {std::vector<int>(n)};
		for (int j = 1; (1 << j) <= n; j++) {
			sparse.push_back(std::vector<int>(n - (1 << j) + 1));
		}
	}

	void ae(int u, int v) {
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	void dfs(int src) {
		in[src] = ti++;
		sparse[0][in[src]] = src;
		pos[src] = (int)tmp.size();
		tmp.emplace_back(dep[src], src);
		for (auto &nxt : adj[src]) {
			if (nxt == par[src]) continue;
			dep[nxt] = dep[par[nxt] = src] + 1;
			dfs(nxt);
			tmp.emplace_back(dep[src], src);
		}
		out[src] = ti;
	}

	inline int mini(int u, int v) {
		return (dep[u] < dep[v] || (dep[u] == dep[v] && in[u] > in[v])) ? u : v;
	}

	void gen(int root = 0) {
		par[root] = root;
		dfs(root);
		S.init(tmp); 
		for (int j = 1; j < (int)sparse.size(); j++) {
			for (int i = 0; i < (int)sparse[j].size(); i++) {
				sparse[j][i] = mini(sparse[j - 1][i], sparse[j - 1][i + (1 << (j - 1))]);
			}
		}
	}

	int lca(int u, int v) {
		u = pos[u];
		v = pos[v];
		if (u > v) std::swap(u, v);
		return S.query(u, v).second;
	}

	int dist(int u, int v) {
		return dep[u] + dep[v] - 2 * dep[lca(u, v)];
	}

	bool is_ancestor(int anc, int src) {
		return in[anc] <= in[src] && out[anc] >= out[src];
	}

	int get_child(int anc, int src) {
		if (!is_ancestor(anc, src)) return -1;
		int l = in[anc] + 1;
		int r = in[src];
		int d = 31 - __builtin_clz(r - l + 1);
		return mini(sparse[d][l], sparse[d][r - (1 << d) + 1]);
	}
	
	std::vector<std::pair<int, int>> compress(std::vector<int> nodes) {
		auto cmp = [&](int a, int b) {
			return pos[a] < pos[b];
		};
		sort(nodes.begin(), nodes.end(), cmp);
		for (int i = (int)nodes.size() - 2; i >= 0; i--) {
			nodes.push_back(lca(nodes[i], nodes[i + 1]));
		}
		sort(nodes.begin(), nodes.end(), cmp);
		nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());
		std::vector<std::pair<int, int>> ret{{0, nodes[0]}};
		for (int i = 0; i < (int)nodes.size(); i++) {
			rev[nodes[i]] = i;
		}
		for (int i = 1; i < (int)nodes.size(); i++) {
			ret.emplace_back(rev[lca(nodes[i - 1], nodes[i])], nodes[i]);
		}
		return ret;
	}
};

template <class T> struct SegmentTree {
	using U = pair<T, int>;

	const U ID = make_pair(numeric_limits<T>::max(), 1);

	int sz;	
	
	vector<U> st; // min, cnt

	vector<T> lz; // lazy


	void init(int _sz) {
		sz = 1;
		while (sz < _sz) {
			sz <<= 1;
		}
		st.assign(2 * sz, make_pair(0, 1));
		lz.assign(2 * sz, 0);
		for (int i = sz - 1; i >= 1; --i) {
			pull(i);
		}
	}

	U comb(U x, U y) {
		U res;
		if (x.first < y.first) {
			res = x;
		} else if (x.first > y.first) {
			res = y;
		} else {
			res.first = x.first;
			res.second = x.second + y.second;
		}
		return res;
	}

	void pull(int i) {
		st[i] = comb(st[2 * i], st[2 * i + 1]);
	}

	void push(int i, int l, int r) {
		if (lz[i] == 0) {
			return;
		}
		st[i].first += lz[i];
		if (l != r) {
			for (int j = 0; j < 2; ++j) {
				lz[2 * i + j] += lz[i];
			}
		}
		lz[i] = 0;
	}

	void upd(int lo, int hi, T inc, int i = 1, int l = 0, int r = -1) {
		if (r == -1) {
			r += sz;
		}
		push(i, l, r);
		if (r < lo || hi < l) {

		} else if (lo <= l && r <= hi) {
			lz[i] = inc;
			push(i, l, r);
		} else {
			int m = (l + r) >> 1;
			upd(lo, hi, inc, 2 * i, l, m);
			upd(lo, hi, inc, 2 * i + 1, m + 1, r);
			pull(i);
		}
	}

	U query(int lo, int hi, int i = 1, int l = 0, int r = -1) {
		if (r == -1) {
			r += sz;
		}
		push(i, l, r);
		if (r < lo || hi < l) {
			return ID;
		} else if (lo <= l && r <= hi) {
			return st[i];
		} else {
			int m = (l + r) >> 1;
			return comb(query(lo, hi, 2 * i, l, m), query(lo, hi, 2 * i + 1, m + 1, r));
		}
	}

	int zeros(int lo, int hi) {
		auto res = query(lo, hi);
		if (res.first == 0) {
			return res.second;
		} else {
			return 0;
		}
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, q;
	cin >> n >> q;
	LCARMQ L;
	L.init(n);
	vector<vector<int>> g(n);
	for (int i = 0; i < n - 1; ++i) {
		int u, v;
		cin >> u >> v;
		--u, --v;
		g[u].push_back(v);
		g[v].push_back(u);
		L.ae(u, v);
	}	
	vector<int> in(n);
	vector<int> out(n);
	int ti = 0;
	function<void(int, int)> dfs = [&](int u, int p) {
		in[u] = ti++;
		for (int v : g[u]) {
			if (v != p) {
				dfs(v, u);
			}
		}
		out[u] = ti - 1;
	};
	dfs(0, -1);
	L.gen(0);
	set<pair<int, int>> used;
	SegmentTree<int> seg;
	seg.init(n);	
	while (q--) {
		int u, v;
		cin >> u >> v;
		--u, --v;
		if (u > v) {
			swap(u, v);
		}
		auto add = [&](int u, int v, int t) {
			int lca = L.lca(u, v);
			if (lca == v) {
				swap(u, v);
			}
			if (lca == u) {
				int child = L.get_child(u, v);
				seg.upd(in[child], out[child], t);
				seg.upd(in[v], out[v], -t);
			} else {
				seg.upd(0, n - 1, t);
				seg.upd(in[u], out[u], -t);
				seg.upd(in[v], out[v], -t);
			}
		};
		if (used.count(make_pair(u, v))) {
			used.erase(make_pair(u, v));
			add(u, v, -1);
		} else {
			used.emplace(u, v);
			add(u, v, 1);
		}
		cout << seg.zeros(0, n - 1) << '\n';
	}
	return 0;
}

Back to top page