#include<bits/stdc++.h>
#define pb push_back
#define int long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vc vector<char>
#define vb vector<bool>
#define mii map<int,int>
#define f0r(i,n) for(int i=0;i<n;i++)
#define FOR(i,k,n) for(int i=k;i<n;i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define in(a) int a; cin>>a
#define in2(a,b) int a,b; cin>>a>>b
#define in3(a,b,c) int a,b,c; cin>>a>>b>>c
#define in4(a,b,c,d) int a,b,c,d; cin>>a>>b>>c>>d
#define vin(v,n); vi v(n); f0r(i,n){cin>>v[i];}
#define out(a) cout<<a<<'\n'
#define out2(a,b) cout<<a<<' '<<b<<'\n'
#define out3(a,b,c) cout<<a<<' '<<b<<' '<<c<<'\n'
#define out4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n'
#define vout(v) cout<<#v<<' '; for(auto u : v){cout<<u<<' ';} cout<<'\n'
#define dout(a) cout<<a<<' '<<#a<<'\n'
#define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<'\n'
#define yn(x); if(x){cout<<"Yes"<<'\n';}else{cout<<"No"<<'\n';}
const int leg = 1e9 + 7;
const int mod = 998244353;
using namespace std;
const int mxn = 255;
int start[mxn];
int finish[mxn];
int timer = 0;
vvi adj(mxn);
vb vis(mxn);
vi dfs_order;
vi depth(mxn);
vi par(mxn);
void euler_tour(int x, int from){
dfs_order.pb(x);
par[x] = from;
if(x != 1)depth[x] = depth[from] + 1;
timer++;
start[x] = timer;
for(auto u : adj[x]){
if(u != from)euler_tour(u, x);
}
finish[x] = timer;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
//ifstream cin(".in");
//ofstream cout(".out");
int tt;
cin>>tt;
f0r(ttt, tt){
in(n);
FOR(i, 1, n+1)adj[i].clear();
f0r(i,n-1){
in2(a,b);
adj[a].pb(b);
adj[b].pb(a);
}
in(m);
if(tt <= 20 && n <= 250 && m <= 100){
FOR(i, 1, n+1)vis[i] = 0;
FOR(i, 1, n+1)depth[i] = 0;
FOR(i, 1, n+1)par[i] = -1;
dfs_order.clear();
vpii paths;
f0r(i, m){
in2(a,b);
paths.pb({a,b});
}
euler_tour(1, -1);
//vout(dfs_order);
vi loc(n+1);
f0r(i, n){
loc[dfs_order[i]] = i;
}
int spt[n][10];
f0r(i,n)spt[i][0] = depth[dfs_order[i]];
FOR(j, 1, 10){
f0r(i, n - (1 << j) + 1){
spt[i][j] = min(spt[i][j-1], spt[i + (1 << (j-1))][j-1]);
}
}
bool ans = 1;
//vout(par);
f0r(i, m){
FOR(j, i+1, m){
//construct path i
int s1 = loc[paths[i].first];
int e1 = loc[paths[i].second];
int lg = floor(log2(e1 - s1 + 1));
int mnd = min(spt[s1][lg], spt[e1 - (1 << lg) + 1][lg]);
vi p1;
int cur = paths[i].first;
if(depth[cur] != mnd)p1.pb(cur);
while(depth[cur] > mnd){
cur = par[cur];
if(depth[cur] != mnd)p1.pb(cur);
}
p1.pb(cur);
vi tmp;
cur = paths[i].second;
if(depth[cur] != mnd)tmp.pb(cur);
while(depth[cur] > mnd){
cur = par[cur];
if(depth[cur] != mnd)tmp.pb(cur);
}
reverse(all(tmp));
for(auto u : tmp)p1.pb(u);
//construct path j
s1 = loc[paths[j].first];
e1 = loc[paths[j].second];
lg = floor(log2(e1 - s1 + 1));
mnd = min(spt[s1][lg], spt[e1 - (1 << lg) + 1][lg]);
vi p2;
cur = paths[j].first;
if(depth[cur] != mnd)p2.pb(cur);
while(depth[cur] > mnd){
cur = par[cur];
if(depth[cur] != mnd)p2.pb(cur);
}
p2.pb(cur);
vi tmp2;
cur = paths[j].second;
if(depth[cur] != mnd)tmp2.pb(cur);
while(depth[cur] > mnd){
cur = par[cur];
if(depth[cur] != mnd)tmp2.pb(cur);
}
reverse(all(tmp2));
for(auto u : tmp2)p2.pb(u);
//vout(p1);
//vout(p2);
//now check if the paths are ok
vector<set<int>> deg(n+1);
f0r(k, p1.size() - 1){
deg[p1[k]].insert(p1[k+1]);
deg[p1[k+1]].insert(p1[k]);
}
f0r(k, p2.size() - 1){
deg[p2[k]].insert(p2[k+1]);
deg[p2[k+1]].insert(p2[k]);
}
bool branch = 0;
f0r(k, n+1){
if(deg[k].size() > 2)branch = 1;
}
if(!branch){
if(find(all(p1), p2[0]) != p1.end() && find(all(p1), p2[p2.size() - 1]) != p1.end()){
ans = 0;
}
else{
vi nxt(n+1);
f0r(k, p1.size() - 1){
nxt[p1[k]] = p1[k+1];
}
//vout(nxt);
f0r(k, p2.size() - 1){
if(nxt[p2[k+1]] == p2[k])ans = 0;
}
}
}
}
}
yn(ans);
}
else{
vpii v;
vector<pair<pii,int>>w;
f0r(i,m){
in2(a,b);
v.pb({min(a,b),max(a,b)});
w.pb({{min(a,b),max(a,b)}, (a > b)});
}
sort(all(v));
sort(all(w));
int mx = -1;
bool ok = 1;
f0r(i,m){
//out3(w[i].first.first, w[i].first.second, w[i].second);
}
f0r(i,m){
if(v[i].second <= mx){
ok = 0;
break;
}
else{
mx = v[i].second;
}
}
mx = -1;
int mx2 = -1;
f0r(i, m){
if(w[i].second){
if(w[i].first.first < mx)ok = 0;
else mx2 = w[i].first.second;
}
else{
if(w[i].first.first < mx2)ok = 0;
else mx = w[i].first.second;
}
}
yn(ok);
}
}
}
Compilation message
jail.cpp: In function 'int main()':
jail.cpp:11:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | #define f0r(i,n) for(int i=0;i<n;i++)
......
149 | f0r(k, p1.size() - 1){
| ~~~~~~~~~~~~~~~~
jail.cpp:149:6: note: in expansion of macro 'f0r'
149 | f0r(k, p1.size() - 1){
| ^~~
jail.cpp:11:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | #define f0r(i,n) for(int i=0;i<n;i++)
......
153 | f0r(k, p2.size() - 1){
| ~~~~~~~~~~~~~~~~
jail.cpp:153:6: note: in expansion of macro 'f0r'
153 | f0r(k, p2.size() - 1){
| ^~~
jail.cpp:11:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | #define f0r(i,n) for(int i=0;i<n;i++)
......
168 | f0r(k, p1.size() - 1){
| ~~~~~~~~~~~~~~~~
jail.cpp:168:8: note: in expansion of macro 'f0r'
168 | f0r(k, p1.size() - 1){
| ^~~
jail.cpp:11:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | #define f0r(i,n) for(int i=0;i<n;i++)
......
172 | f0r(k, p2.size() - 1){
| ~~~~~~~~~~~~~~~~
jail.cpp:172:8: note: in expansion of macro 'f0r'
172 | f0r(k, p2.size() - 1){
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
6 ms |
592 KB |
Output is correct |
| 5 |
Correct |
12 ms |
860 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
592 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
592 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
592 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
592 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
592 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
6 ms |
592 KB |
Output is correct |
| 5 |
Correct |
12 ms |
860 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
592 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
