Submission #609705

#TimeUsernameProblemLanguageResultExecution timeMemory
609705HamletPetrosyanJail (JOI22_jail)C++17
72 / 100
5090 ms427108 KiB
/// #if (code == true)

#include <bits/stdc++.h>
using namespace std;

#define pll pair<long long, long long>
#define len(a) ((int)((a).size()))
#define all(a) a.begin(), a.end()
#define add push_back
#define mkp make_pair
#define ll long long
#define fr first
#define sc second

const long long INF = 1000000000ll * 1000000003ll;
const long long MOD = 1000000007ll;
const int N = 2e5 + 5;

ll n, m, s[N], t[N];
vector<int> g[N], dir[N], f[N], h[N];
int color[N];

ll ls[N][25], tin[N], tout[N], timer = 0;

void dfs(int v, int p){
	ls[v][0] = p;
	for(int i = 1; i <= 20; i++){
		ls[v][i] = ls[ls[v][i - 1]][i - 1];
	}

	tin[v] = ++timer;
	for(int i = 0; i < len(g[v]); i++){
		int to = g[v][i];
		if(to == p) continue;
		dfs(to, v);
	}
	tout[v] = ++timer;
}

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

int lsa(int a, int b){
	if(isa(a, b)) return a;
	if(isa(b, a)) return b;
	for(int i = 20; i >= 0; i--){
		if(isa(ls[a][i], b)) continue;
		a = ls[a][i];
	}
	return ls[a][0];
}

void check(int i, int j){
	int a = lsa(s[i], t[i]);
	int b = lsa(s[j], t[j]);
	if(isa(a, s[j]) && (isa(s[j], s[i]) || isa(s[j], t[i]))){
		dir[i].add(j);
	}
	if(isa(b, t[i]) && (isa(t[i], s[j]) || isa(t[i], t[j]))){
		dir[i].add(j);
	}
}

bool check_cycle(int v){
	color[v] = 1;
	for(int i = 0; i < len(dir[v]); i++){
		int to = dir[v][i];
		if(color[to] == 2) continue;
		if(color[to] == 1) {
			return true;
		}
		if(check_cycle(to)){
			return true;
		}
	}
	color[v] = 2;
	return false;
}

void solve(){
	timer = 0;

	cin >> n;
	for(int i = 1; i <= n; i++){
		g[i].clear();
		h[i].clear();
		f[i].clear();
	}
	for(int i = 0; i < m; i++){
		dir[i].clear();
		color[i] = 0;
	}

	int u, v;
	for(int i = 1; i < n; i++){
		cin >> u >> v;
		g[u].add(v);
		g[v].add(u);
	}
	dfs(1, 1);
	cin >> m;
	for(int i = 0; i < m; i++){
		cin >> s[i] >> t[i];
		f[s[i]].add(i);
		h[t[i]].add(i);
	}
	int lc, now;
	for(int i = 0; i < m; i++){
		lc = lsa(s[i], t[i]);
		now = s[i];
		if(len(h[s[i]]) && h[s[i]][0] != i){
			dir[h[s[i]][0]].add(i);
		}
		if(s[i] != lc){
			do {
				now = ls[now][0];
				if(len(f[now]) && f[now][0] != i){
					dir[i].add(f[now][0]);
				}
				if(len(h[now]) && h[now][0] != i){
					dir[h[now][0]].add(i);
				}
			} while(now != lc);
		}
		now = t[i];
		while(now != lc){
			if(len(f[now]) && f[now][0] != i){
				dir[i].add(f[now][0]);
			}
			if(len(h[now]) && h[now][0] != i){
				dir[h[now][0]].add(i);
			}
			now = ls[now][0];
		}
	}

//	for(int i = 0; i < m; i++){
//		cout << i << ": ";
//		for(int j = 0; j < len(dir[i]); j++){
//			cout << dir[i][j] << " ";
//		}
//		cout << endl;
//	}

//	for(int i = 0; i < m; i++){
//		for(int j = 0; j < m; j++){
//			if(i == j) continue;
//			check(i, j);
//		}
//	}
	for(int i = 0; i < m; i++){
		if(color[i] == 0) {
			if(check_cycle(i)){
				cout << "No\n";
				return;
			}
		}
	}

	cout << "Yes\n";
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int _ = 1;
	// cout << fixed;
	// cout.precision(15);

	cin >> _ ;
	while(_--) solve();
	return 0;
}

/// #else
/// #include <bits/stdc++.h> using namespace std; int main() { cout << "Hello World!"; }
/// #endif
#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...