Submission #602541

#TimeUsernameProblemLanguageResultExecution timeMemory
602541TigryonochekkJail (JOI22_jail)C++17
0 / 100
22 ms3396 KiB
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <string>
using namespace std;
#define ll long long
#define pii pair<int, int>
const int N = 1.2e5 + 2, lgN = 17;

int n;
int ln;
vector<int> g[N];
int p[N];
int tin[N], tout[N];
int timer;
int d[N][lgN];

int m;
int b[N], w[N];

void cleaning() {
	for (int i = 1; i <= n; i++) {
		g[i].clear();
	}
	fill(p + 1, p + n + 1, 0);
	fill(tin, tin + n + 1, 0);
	fill(tout, tout + n + 1, 0);
	timer = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < ln; j++) {
			d[i][j] = 0;
		}
	}
}

void dfs(int v) {
	tin[v] = timer++;
	for (int to : g[v]) {
		if (p[v] == to) continue;
		p[to] = v;
		d[to][0] = v;
		for (int i = 1; i < ln; i++) {
			d[to][i] = d[d[to][i - 1]][i - 1];
		}
		dfs(to);
	}
	tout[v] = timer++;
}

bool check(int a, int b) {
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lca(int a, int b) {
	if (check(a, b)) return a;
	if (check(b, a)) return b;
	for (int i = ln - 1; i >= 0; i--) {
		if (!check(d[a][i], b))
			a = d[a][i];
	}
	return p[a];
}

bool belong(int a, int b, int c) {
	return check(lca(a, b), c) && (check(c, a) || check(c, b));
}

void solve() {
	cin >> n;
	ln = log2(n) + 1;
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	cin >> m;
	for (int i = 1; i <= m; i++) {
		cin >> b[i] >> w[i];
	}
	p[1] = 1;
	for (int i = 0; i < ln; i++) {
		d[1][i] = 1;
	}
	dfs(1);
	if ((belong(b[1], w[1], b[2]) && belong(b[2], w[2], b[1])) || (belong(b[1], w[1], w[2]) && belong(b[2], w[2], w[1])))
		cout << "No\n";
	else
		cout << "Yes\n";
	cleaning();
}

int main() {
	int t = 1;
	cin >> t;
	while (t--) 
		solve();
	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...