#include <bits/stdc++.h>
#define all(a) (a).begin(), (a).end()
using namespace std;
using namespace chrono;
struct segtree {
vector<int> tree;
int offset = 1;
segtree(int n) {
while (offset < n) offset *= 2;
tree.resize(offset*2);
}
void update(int i, int x) {
tree[i += offset] = x;
while (i >>= 1) tree[i] = min(tree[i*2], tree[i*2 + 1]);
}
int query(int v, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return tree[v];
if (qr < l || r < ql) return 1e9;
int mid = (l+r)/2;
return min(
query(2*v, l, mid, ql, qr),
query(2*v+1, mid+1, r, ql, qr)
);
}
int query(int l, int r) {
return query(1, 0, offset - 1, l, r);
}
};
void solve() {
int n,m; cin >> n;
for (int i = 0, a, b; i < n-1; cin >> a >> b, i++);
cin >> m;
int L[m], R[m];
int pref[n] = {};
for (int i = 0; i < m; i++) {
cin >> L[i] >> R[i];
if (L[i] > R[i]) swap(L[i], R[i]);
L[i]--, R[i]--;
pref[L[i]]++;
if (R[i] != n-1) pref[R[i] + 1]--;
}
for (int i = 1; i < n; i++) {
pref[i] += pref[i-1];
}
segtree s(n);
for (int i = 0; i < n; i++)
s.update(i, pref[i]);
for (int i = 0; i < m; i++) {
int mn = s.query(L[i], R[i]);
if (mn >= 2) {
cout << "No\n";
return;
}
}
cout << "Yes\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t; while (t--)
solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |