제출 #1333260

#제출 시각아이디문제언어결과실행 시간메모리
1333260ppmn_6Jail (JOI22_jail)C++20
5 / 100
396 ms126340 KiB
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
// https://codeforces.com/blog/entry/79148
class Timer: chrono::high_resolution_clock {
    const time_point start_time;
public:
    Timer(): start_time(now()) {}
    rep elapsed_time() const {
		return chrono::duration_cast<chrono::milliseconds>(now() - start_time).count();
	}
} timer;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int q;
	cin >> q;
	while (q--) {
		int n, m;
		cin >> n;
		vector<vector<int>> tree(n + 1);
		for (int i = 1; i < n; i++) {
			int u, v;
			cin >> u >> v;
			tree[u].push_back(v);
			tree[v].push_back(u);
		}
		vector<int> sz(n + 1, 1), heavy(n + 1), head(n + 1), pos(n + 1), depth(n + 1), par(n + 1);
		int cur = 0;
		depth[1] = 0;
		auto dfs = [&] (auto self, int u, int p)->void {
			int cur_max = 0;
			par[u] = p;
			for (auto &v : tree[u]) {
				if (v != p) {
					depth[v] = depth[u] + 1;
					self(self, v, u);
					sz[u] += sz[v];
					if (sz[v] > cur_max) {
						cur_max = sz[v];
						heavy[u] = v;
					}
				}
			}
		};
		auto decomp = [&] (auto self, int u, int p, int h)->void {
			head[u] = h;
			pos[u] = cur;
			cur++;
			if (heavy[u]) {
				self(self, heavy[u], u, h);
			}
			for (auto &v : tree[u]) {
				if (v != p && v != heavy[u]) {
					self(self, v, u, v);
				}
			}
		};
		dfs(dfs, 1, 0);
		decomp(decomp, 1, 0, 1);
		cin >> m;
		vector<pair<int, int>> queries(m);
		for (int i = 0; i < m; i++) {
			cin >> queries[i].first >> queries[i].second;
		}
		vector<vector<int>> graph(8 * n + m);
		auto build = [&] (auto self, int p, int rl, int rr, bool flag)->void {
			if (rl == rr) {
				return;
			}
			int u = flag * 4 * n + p, l = flag * 4 * n + p * 2, r = flag * 4 * n + p * 2 + 1;
			if (flag) {
				graph[u].push_back(l);
				graph[u].push_back(r);
			}
			else {
				graph[l].push_back(u);
				graph[r].push_back(u);
			}
			int rm = (rl + rr) / 2;
			self(self, p * 2, rl, rm, flag);
			self(self, p * 2 + 1, rm + 1, rr, flag);
		};
		build(build, 1, 0, n - 1, 0);
		build(build, 1, n, 2 * n - 1, 1);
		auto add = [&] (auto self, int p, int rl, int rr, int l, int r, bool flag, bool dir, int from)->void {
			int u = flag * 4 * n + p;
			if (rl == l && rr == r) {
				if (dir) {
					graph[from].push_back(u);
				}
				else {
					graph[u].push_back(from);
				}
			}
			else {
				int rm = (rl + rr) / 2;
				if (l <= rm) {
					self(self, p * 2, rl, rm, l, min(r, rm), flag, dir, from);
				}
				if (r > rm) {
					self(self, p * 2 + 1, rm + 1, rr, max(rm + 1, l), r, flag, dir, from);
				}
			}
		};
		auto update = [&] (int u, int v, int from)->void {
			from += 8 * n;
			add(add, 1, 0, n - 1, pos[u], pos[u], 0, 1, from);
			add(add, 1, 0, n - 1, pos[v], pos[v], 0, 0, from);
			add(add, 1, n, 2 * n - 1, n + pos[u], n + pos[u], 1, 1, from);
			add(add, 1, n, 2 * n - 1, n + pos[v], n + pos[v], 1, 0, from);
			if (depth[u] > depth[v]) {
				swap(u, v);
			}
			v = par[v];
			bool flag = 0;
			while (head[u] != head[v]) {
				if (depth[u] > depth[v]) {
					swap(u, v);
					if (!flag) {
						flag = 1;
						v = par[v];
						continue;
					}
				}
				add(add, 1, 0, n - 1, pos[head[v]], pos[v], 0, 0, from);
				add(add, 1, n, 2 * n - 1, n + pos[head[v]], n + pos[v], 1, 1, from);
				v = par[head[v]];
			}
			if (depth[u] > depth[v]) {
				swap(u, v);
				if (!flag) {
					flag = 1;
					v = par[v];
				}
			}
			if (flag) {
				add(add, 1, 0, n - 1, pos[u], pos[v], 0, 0, from);
				add(add, 1, n, 2 * n - 1, n + pos[u], n + pos[v], 1, 1, from);
			}
			else {
				if (u == v) {
					return;
				}
				add(add, 1, 0, n - 1, pos[u] + 1, pos[v], 0, 0, from);
				add(add, 1, n, 2 * n - 1, n + pos[u] + 1, n + pos[v], 1, 1, from);
			}
		};
		for (int i = 0; i < m; i++) {
			auto &[u, v] = queries[i];
			update(u, v, i);
		}
		vector<int> vis(8 * n + m, 0);
		bool flag = 1;
		auto dfs2 = [&] (auto self, int u)->void {
			vis[u] = 1;
			for (auto &v : graph[u]) {
				if (vis[v] == 1) {
					flag = 0;
				}
				if (!vis[v]) {
					self(self, v);
				}
				if (!flag) {
					return;
				}
			}
			vis[u] = 2;
		};
		for (int i = 0; i < 8 * n + m; i++) {
			if (!vis[i]) {
				dfs2(dfs2, i);
				if (!flag) {
					break;
				}
			}
		}
		/*for (int i = 0; i < 8 * n + m; i++) {
			for (auto &j : graph[i]) {
					cout << i << " " << j << "\n";
			}
		}*/
		cout << (flag ? "Yes" : "No") << "\n";
	}
	
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...