Submission #1015976

#TimeUsernameProblemLanguageResultExecution timeMemory
1015976vjudge3Jail (JOI22_jail)C++17
100 / 100
1231 ms393812 KiB
#include <bits/stdc++.h>
using namespace std;
 
vector<int> g[120005];
vector<pair<int, int>> h[360005][20];
int lift[120005][20], d[120005], tin[120005], tout[120005], timer, lg, col[360005][20], in[120005], out[120005];
bool ans = true;
 
void dfs(int u, int p) {
	tin[u] = ++timer;
	lift[u][0] = p;
	for (int i = 1; i <= lg; i++) lift[u][i] = lift[lift[u][i-1]][i-1];
	for (auto& v : g[u]) if (v != p) {
		d[v] = d[u]+1;
		dfs(v, u);
	}
	tout[u] = timer;
}
 
bool anc(int u, int v) {
	return !u || (tin[u] <= tin[v] && tout[u] >= tout[v]);
}
 
int lca(int s, int t) {
	if (anc(s, t)) return s;
	for (int i = lg; i >= 0; i--) if (!anc(lift[s][i], t)) s = lift[s][i];
	return lift[s][0];
}
 
void dfs_cyc(int u, int k) {
	col[u][k] = 1;
	for (auto& [v, l] : h[u][k]) if (col[v][l] != 2) {
		if (col[v][l] == 1) ans = false;
		else dfs_cyc(v, l);
	}
	col[u][k] = 2;
}

void add(int u, int k, int v, int l) {
	h[u][k].push_back({v, l});
}
 
void solve() {
	int n, m;
	cin >> n;
	lg = __lg(n);
	timer = 0;
	ans = 1;
	for (int i = 1; i <= n; i++) {
		g[i].clear();
		d[i] = tin[i] = tout[i] = in[i] = out[i] = 0;
		for (int j = 0; j <= lg; j++) lift[i][j] = 0;
	}
	for (int i = 1; i <= n*3; i++)
		for (int j = 0; j <= lg; j++) {
			h[i][j].clear();
			col[i][j] = 0;
		}
	for (int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	cin >> m;
	vector<pair<int, int>> path (m);
	bool ok = true;
	for (int i = 0; i < m; i++) {
		auto& [s, t] = path[i];
		cin >> s >> t;
		out[s] = i+1;
		in[t] = i+1;
	}
	for (int i = 0; i < m; i++) {
		auto [s, t] = path[i];
		if (in[s]) add(in[s], 0, i+1, 0);
		if (out[t]) add(i+1, 0, out[t], 0);
	}
	if (!ok) {
		cout << "No\n";
		return;
	}
	dfs(1, 0);
	for (int i = 1; i <= m; i++) {
		auto [u, v] = path[i-1];
		int t = lca(u, v);
		if (u != t && v != t) add(i, 0, n+t, 0);
		if (u != t && (u = lift[u][0]) != t) {
			int diff = d[u] - d[t], l = __lg(diff);
			add(i, 0, n+u, l);
			diff -= 1<<l;
			for (int j = 0; j <= lg; j++) if (diff & (1<<j)) u = lift[u][j];
			add(i, 0, n+u, l);
		}
		if (v != t) {
			int diff = d[v] - d[t], l = __lg(diff);
			add(i, 0, n+v, l);
			diff -= 1<<l;
			for (int j = 0; j <= lg; j++) if (diff & (1<<j)) v = lift[v][j];
			add(i, 0, n+v, l);
		}
	}
	for (int i = 1; i <= n; i++) for (int j = lg; j >= 1; j--) {
		add(n+i, j, n+i, j-1);
		if (lift[i][j-1]) add(n+i, j, n+lift[i][j-1], j-1);
	}
	for (int i = 0; i < m; i++) add(n+path[i].first, 0, i+1, 0);
	for (int i = 1; i <= m; i++) {
		auto [u, v] = path[i-1];
		int t = lca(u, v);
		if (u != t && v != t) add(n*2+t, 0, i, 0);
		if (u != t) {
			int diff = d[u] - d[t], l = __lg(diff);
			add(n*2+u, l, i, 0);
			diff -= 1<<l;
			for (int j = 0; j <= lg; j++) if (diff & (1<<j)) u = lift[u][j];
			add(n*2+u, l, i, 0);
		}
		if (v != t && (v = lift[v][0]) != t) {
			int diff = d[v] - d[t], l = __lg(diff);
			add(n*2+v, l, i, 0);
			diff -= 1<<l;
			for (int j = 0; j <= lg; j++) if (diff & (1<<j)) v = lift[v][j];
			add(n*2+v, l, i, 0);
		}
	}
	for (int i = 1; i <= n; i++) for (int j = lg; j >= 1; j--) {
		add(n*2+i, j-1, n*2+i, j);
		if (lift[i][j-1]) add(n*2+lift[i][j-1], j-1, n*2+i, j);
	}
	for (int i = 0; i < m; i++) add(i+1, 0, n*2+path[i].second, 0);
	for (int i = 1; i <= n; i++) if (!col[i][0]) dfs_cyc(i, 0);
	cout << (ans ? "Yes\n" : "No\n");
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int q;
	cin >> q;
	while (q--) 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...