#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define pii pair<int, int>
#define st first
#define nd second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
struct SegTree {
int T=1;
vector<set<int>> t;
void build(int n) {
T=1;
while(T<=n) T*=2;
t.resize(2*T);
for(int i=0;i<2*T;i++) t.clear();
}
vector<int> query(int l, int r) {
l+=T, r+=T;
vector<int> ret;
for(int x:t[l]) ret.pb(x);
if(l!=r) for(int x:t[r]) ret.pb(x);
while(l/2!=r/2) {
if(l%2==0) for(int x:t[l+1]) ret.pb(x);
if(r%2==1) for(int x:t[r-1]) ret.pb(x);
l/=2;
r/=2;
}
return ret;
}
void add(int x, int val) {
x+=T;
while(x) {
t[x].insert(val);
x/=2;
}
}
void remove(int x, int val) {
x+=T;
while(x) {
t[x].erase(val);
x/=2;
}
}
};
struct SegTree2 {
int T = 1;
vector<set<int>> t;
void build(int n) {
T=1;
while(T<=n) T*=2;
t.resize(2*T);
for(int i=0;i<2*T;i++) t.clear();
}
void add(int l, int r, int val) {
l+=T, r+=T;
t[l].insert(val);
if(l!=r) t[r].insert(val);
while(l/2!=r/2) {
if(l%2==0) t[l+1].insert(val);
if(r%2==1) t[r-1].insert(val);
l/=2;
r/=2;
}
}
void remove(int l, int r, int val) {
l+=T, r+=T;
t[l].erase(val);
if(l!=r) t[r].insert(val);
while(l/2!=r/2) {
if(l%2==0) t[l+1].erase(val);
if(r%2==1) t[r-1].erase(val);
l/=2;
r/=2;
}
}
vector<int> query(int x) {
vector<int> ret;
x+=T;
while(x) {
for(int y:t[x]) ret.pb(y);
x/=2;
}
return ret;
}
};
vector<int> G[120009];
vector<int> G2[120009];
int tin[120009], tout[120009], T;
int jp2[120009][20];
int deg[120009];
pii tab[120009];
int col[120009];
int dep[120009];
int p[120009];
int heavy[120009];
int pos[120009], P;
int head[120009];
int dfs(int x, int y) {
p[x] = y;
dep[x] = dep[y]+1;
int sz = 1, max_sz=0;
tin[x] = ++T;
jp2[x][0] = y;
for(int i=1;i<20;i++) jp2[x][i] = jp2[jp2[x][i-1]][i-1];
for(int z:G[x]) if(z!=y) {
int c_sz = dfs(z, x);
//cout << x << " " << z << " " << c_sz << "\n";
//cout << max_sz << "\n";
sz += c_sz;
if(c_sz>max_sz) {
max_sz = c_sz;
//cout << "setting heavy to: " << z << "\n";
heavy[x] = z;
}
}
tout[x] = ++T;
return sz;
}
void decompose(int x, int h) {
head[x] = h;
pos[x] = ++P;
//cout << "pos: " << x << " " << pos[x] << "\n";
//cout << heavy[x] << "\n";
if(heavy[x]) {
decompose(heavy[x], h);
}
for(int y:G[x]) {
if(y!=p[x]&&y!=heavy[x]) decompose(y, y);
}
}
bool is_ancestor(int x, int y) {
return tin[x]<=tin[y]&&tout[x]>=tout[y];
}
int lca(int x, int y) {
if(is_ancestor(x, y)) return x;
if(is_ancestor(y, x)) return y;
for(int i=19;i>=0;i--) {
if(!is_ancestor(jp2[x][i], y)) {
x = jp2[x][i];
}
}
return jp2[x][0];
}
bool is_on_path(int x, int a, int b) {
return is_ancestor(a, x)&&is_ancestor(x, b);
}
bool f(int x, int a, int b) {
int y = lca(a, b);
//cerr << "lca: " << a << " " << b << " " << y << "\n";
//cerr << "checking: " << x << " " << a << " " << b << " " << (is_on_path(x, y, a)||is_on_path(x, y, b)) << "\n";
return is_on_path(x, y, a)||is_on_path(x, y, b);
}
SegTree seg1;
SegTree2 seg2;
vector<int> hld_query(int a, int b) {
//cout << "hld_query: " << a << " " << b << "\n";
vector<int> ret;
for (; head[a] != head[b]; b=p[head[b]]) {
if (dep[head[a]] > dep[head[b]]) swap(a, b);
for(int x:seg1.query(pos[head[b]], pos[b])) ret.pb(x);
}
if (dep[a] > dep[b]) swap(a, b);
for(int x:seg1.query(pos[a], pos[b])) ret.pb(x);
return ret;
}
void hld_add(int a, int b, int val) {
//cout << "hld_query: " << a << " " << b << "\n";
vector<int> ret;
for (; head[a] != head[b]; b=p[head[b]]) {
if (dep[head[a]] > dep[head[b]]) swap(a, b);
seg2.add(pos[head[b]], pos[b], val);
}
if (dep[a] > dep[b]) swap(a, b);
seg2.add(pos[a], pos[b], val);
}
void hld_remove(int a, int b, int val) {
//cout << "hld_query: " << a << " " << b << "\n";
vector<int> ret;
for (; head[a] != head[b]; b=p[head[b]]) {
if (dep[head[a]] > dep[head[b]]) swap(a, b);
seg2.remove(pos[head[b]], pos[b], val);
}
if (dep[a] > dep[b]) swap(a, b);
seg2.remove(pos[a], pos[b], val);
}
bool dfs2(int x) {
//cout << "dfs: " << x << "\n";
col[x] = 1;
vector<int> v1 = hld_query(tab[x].st, tab[x].nd);
for(int y:v1){
if(y==x) continue;
//cout << "sprawdzam1: "<< y << "\n";
if(col[y]==1) return false;
}
for(int y:v1) {
if(y==x) continue;
if(!dfs2(y)) return false;
}
//cout << "v2 dla: "<< tab[x].nd << "\n";
vector<int> v2 = seg2.query(pos[tab[x].nd]);
for(int y:v2) {
if(y==x) continue;
//cout << "sprawdzam2: "<< y << "\n";
if(col[y]==1) return false;
}
for(int y:v2) {
if(y==x) continue;
if(!dfs2(y)) return false;
}
col[x] = 2;
seg1.remove(pos[tab[x].st], x);
hld_remove(tab[x].st, tab[x].nd, x);
return true;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int q=1;
cin >> q;
while(q--) {
int n, m;
cin >> n;
for(int i=1;i<=n;i++) {
G[i].clear();
head[i] = 0;
heavy[i] = 0;
dep[i] = 0;
p[i] = 0;
}
for(int i=0;i<n-1;i++) {
int a, b;
cin >> a >> b;
G[a].pb(b);
G[b].pb(a);
}
tin[0] = T = 0;
dfs(1, 0);
decompose(1, 1);
tout[0] = T;
cin >> m;
for(int i=0;i<m;i++) {
G2[i].clear();
deg[i] = 0;
col[i] = 0;
}
seg1.build(n+9);
seg2.build(n+9);
for(int i=0;i<m;i++) {
cin >> tab[i].st >> tab[i].nd;
seg1.add(pos[tab[i].st], i);
hld_add(tab[i].st, tab[i].nd, i);
}
bool ans = true;
for(int i=0;i<m;i++) {
if(!col[i]) {
ans&=dfs2(i);
}
}
if(ans) {
cout << "Yes\n";
} else {
cout << "No\n";
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5972 KB |
Output is correct |
| 2 |
Correct |
3 ms |
6040 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5972 KB |
Output is correct |
| 4 |
Runtime error |
8 ms |
12188 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5912 KB |
Output is correct |
| 2 |
Correct |
2 ms |
5972 KB |
Output is correct |
| 3 |
Runtime error |
9 ms |
12328 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5912 KB |
Output is correct |
| 2 |
Correct |
2 ms |
5972 KB |
Output is correct |
| 3 |
Runtime error |
9 ms |
12328 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5912 KB |
Output is correct |
| 2 |
Correct |
2 ms |
5972 KB |
Output is correct |
| 3 |
Runtime error |
9 ms |
12328 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5912 KB |
Output is correct |
| 2 |
Correct |
2 ms |
5972 KB |
Output is correct |
| 3 |
Runtime error |
9 ms |
12328 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
5972 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5972 KB |
Output is correct |
| 3 |
Correct |
2 ms |
5972 KB |
Output is correct |
| 4 |
Correct |
3 ms |
5972 KB |
Output is correct |
| 5 |
Runtime error |
8 ms |
11988 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5972 KB |
Output is correct |
| 2 |
Correct |
3 ms |
6040 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5972 KB |
Output is correct |
| 4 |
Runtime error |
8 ms |
12188 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
