| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 609632 | HamletPetrosyan | Jail (JOI22_jail) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
}
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();
}
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];
}
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