#include <bits/stdc++.h>
using namespace std;
#define int long long
void add(vector<pair<int,int>> &v, int L, int R) {
if (v.size() > 0 && R+1 == v.back().first) v.back().first = L;
else v.push_back({L, R});
}
const int maxn = 1e6+5, maxN = 4e6+5, lgn = 20, INF = 1e18;
int n, m;
vector<int> ADJ[maxn], adj[maxn];
pair<int,int> a[maxn];
int sz[maxn], fa[maxn], d[maxn], newid[maxn], lim[maxn], cnter = 0;
bool cmp(int x, int y) {
return sz[x] > sz[y];
}
void dfs1(int u) {
sz[u] = 1;
for (int v:ADJ[u]) {
ADJ[v].erase(find(ADJ[v].begin(), ADJ[v].end(), u));
dfs1(v);
sz[u] += sz[v];
}
sort(ADJ[u].begin(), ADJ[u].end(), cmp);
}
void dfs2(int u) {
cnter++;
newid[u] = cnter;
for (int v:ADJ[u]) {
d[cnter+1] = d[newid[u]] + 1;
fa[cnter+1] = newid[u];
dfs2(v);
}
lim[newid[u]] = cnter;
}
pair<int, vector<pair<int,int>>> binlift[maxn][lgn];
void dfs3(int u) {
for (int i=1;i<lgn;i++) {
if (binlift[u][i-1].first==-1 || binlift[binlift[u][i-1].first][i-1].first==-1) break;
binlift[u][i].first = binlift[binlift[u][i-1].first][i-1].first;
binlift[u][i].second = binlift[u][i-1].second;
for (auto [L, R]:binlift[binlift[u][i-1].first][i-1].second) add(binlift[u][i].second, L, R);
}
for (int v:adj[u]) {
binlift[v][0] = {u, {{u, u}}};
dfs3(v);
}
}
vector<pair<int,int>> PATH(int u, int v) {
if (d[u] > d[v]) swap(u, v);
vector<pair<int,int>> U = {{u, u}}, V = {{v, v}};
for (int i=lgn-1;i>=0;i--) if (d[v] - (1<<i) >= d[u]) {
for (auto [L, R]:binlift[v][i].second) add(V, L, R);
v = binlift[v][i].first;
}
if (u==v) return V;
for (int i=lgn-1;i>=0;i--) if (binlift[u][i].first != binlift[v][i].first) {
for (auto [L, R]:binlift[u][i].second) add(U, L, R);
u = binlift[u][i].first;
for (auto [L, R]:binlift[v][i].second) add(V, L, R);
v = binlift[v][i].first;
}
add(V, fa[v], fa[v]);
for (auto [L, R]:U) V.push_back({L, R});
return V;
}
set<int> seg[maxN];
void build(int id, int l, int r) {
seg[id].clear();
if (l==r) return;
int mid = (l+r)/2;
build(id*2, l, mid); build(id*2+1, mid+1, r);
}
void update(int id, int l, int r, int findl, int findr, int val, bool addd) {
if (r<findl || findr<l) return;
if (findl<=l && r<=findr) {
if (addd) seg[id].insert(val);
else seg[id].erase(val);
return;
}
int mid = (l+r)/2;
update(id*2, l, mid, findl, findr, val, addd);
update(id*2+1, mid+1, r, findl, findr, val, addd);
}
vector<int> nxt;
void qry(int id, int l, int r, int target) {
if (r<target || target<l) return;
for (int i:seg[id]) nxt.push_back(i);
if (l==r) return;
int mid = (l+r)/2;
qry(id*2, l, mid, target); qry(id*2+1, mid+1, r, target);
}
int S[maxn], T[maxn], vis[maxn];
bool die = false;
set<int> exist;
void dfs4(int u) {
int s = a[u].first, t = a[u].second;
vis[u] = 1;
vector<pair<int,int>> path = PATH(s, t);
for (auto [L, R]:path) {
int cur = L-1;
while (exist.size() > 0) {
cur = *exist.upper_bound(cur);
if (cur > R) break;
if (cur==s) continue;
int v = S[cur];
// cout << u << " " << v << endl;
if (!vis[v]) dfs4(v);
else if (vis[v]==1) die = true;
if (die) return;
}
}
nxt.clear();
qry(1, 1, n, t);
for (int v:nxt) if (v!=u) {
// cout << u << " " << v << endl;
if (!vis[v]) dfs4(v);
else if (vis[v]==1) die = true;
if (die) return;
}
for (auto [L, R]:path) update(1, 1, n, L, R, u, 0);
exist.erase(s);
vis[u] = 2;
}
void solve() {
cin >> n;
for (int i=1;i<=n;i++) sz[i] = 0, adj[i].clear(), ADJ[i].clear();
cnter = 0;
for (int i=1;i<=n-1;i++) {
int u, v;
cin >> u >> v;
ADJ[u].push_back(v);
ADJ[v].push_back(u);
}
fa[1] = 0, d[1] = 0;
dfs1(1); dfs2(1);
for (int i=1;i<=n;i++) for (int j:ADJ[i]) adj[newid[i]].push_back(newid[j]);
for (int i=1;i<=n;i++) for (int j=0;j<lgn;j++) binlift[i][j] = {-1, {}};
dfs3(1);
// for (int i=1;i<=n;i++) {
// cout << i << endl;
// for (int j=0;j<lgn;j++) {
// cout << binlift[i][j].first << " ";
// for (auto [L, R]:binlift[i][j].second) cout << L << '.' << R << " ";
// cout << endl;
// if (binlift[i][j].first==-1) break;
// }
// cout << endl;
// }
// return;
exist = {INF};
build(1, 1, n);
for (int i=1;i<=n;i++) S[i] = -1, T[i] = -1;
cin >> m;
for (int i=1;i<=m;i++) {
int s, t;
cin >> s >> t;
s = newid[s], t = newid[t];
a[i] = {s, t};
S[s] = T[t] = i;
exist.insert(s);
vector<pair<int,int>> path = PATH(s, t);
for (auto [L, R]:path) update(1, 1, n, L, R, i, 1);
}
for (int i=1;i<=m;i++) vis[i] = 0;
die = false;
for (int i=1;i<=m;i++) if (!vis[i]) {
dfs4(i);
if (die) break;
}
if (die) cout << "No\n";
else cout << "Yes\n";
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
int t;
cin >> t;
while (t--) solve();
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
360 ms |
863104 KB |
Output is correct |
2 |
Correct |
386 ms |
862948 KB |
Output is correct |
3 |
Correct |
325 ms |
863064 KB |
Output is correct |
4 |
Correct |
344 ms |
863568 KB |
Output is correct |
5 |
Correct |
355 ms |
863824 KB |
Output is correct |
6 |
Correct |
372 ms |
863256 KB |
Output is correct |
7 |
Correct |
340 ms |
863312 KB |
Output is correct |
8 |
Correct |
354 ms |
863316 KB |
Output is correct |
9 |
Correct |
439 ms |
868384 KB |
Output is correct |
10 |
Correct |
551 ms |
953936 KB |
Output is correct |
11 |
Correct |
427 ms |
863288 KB |
Output is correct |
12 |
Correct |
401 ms |
864084 KB |
Output is correct |
13 |
Correct |
703 ms |
974676 KB |
Output is correct |
14 |
Correct |
645 ms |
973648 KB |
Output is correct |
15 |
Correct |
915 ms |
992548 KB |
Output is correct |
16 |
Correct |
1843 ms |
1047448 KB |
Output is correct |
17 |
Correct |
865 ms |
1005140 KB |
Output is correct |
18 |
Correct |
629 ms |
979540 KB |
Output is correct |
19 |
Correct |
767 ms |
999188 KB |
Output is correct |
20 |
Correct |
754 ms |
999256 KB |
Output is correct |
21 |
Correct |
784 ms |
1004748 KB |
Output is correct |
22 |
Correct |
531 ms |
962896 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
356 ms |
863192 KB |
Output is correct |
2 |
Correct |
396 ms |
863060 KB |
Output is correct |
3 |
Correct |
397 ms |
863316 KB |
Output is correct |
4 |
Correct |
351 ms |
863224 KB |
Output is correct |
5 |
Correct |
361 ms |
863196 KB |
Output is correct |
6 |
Correct |
362 ms |
863240 KB |
Output is correct |
7 |
Correct |
337 ms |
863320 KB |
Output is correct |
8 |
Correct |
368 ms |
863188 KB |
Output is correct |
9 |
Correct |
362 ms |
863188 KB |
Output is correct |
10 |
Correct |
378 ms |
863316 KB |
Output is correct |
11 |
Correct |
324 ms |
863316 KB |
Output is correct |
12 |
Correct |
359 ms |
863152 KB |
Output is correct |
13 |
Correct |
363 ms |
863172 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
356 ms |
863192 KB |
Output is correct |
2 |
Correct |
396 ms |
863060 KB |
Output is correct |
3 |
Correct |
397 ms |
863316 KB |
Output is correct |
4 |
Correct |
351 ms |
863224 KB |
Output is correct |
5 |
Correct |
361 ms |
863196 KB |
Output is correct |
6 |
Correct |
362 ms |
863240 KB |
Output is correct |
7 |
Correct |
337 ms |
863320 KB |
Output is correct |
8 |
Correct |
368 ms |
863188 KB |
Output is correct |
9 |
Correct |
362 ms |
863188 KB |
Output is correct |
10 |
Correct |
378 ms |
863316 KB |
Output is correct |
11 |
Correct |
324 ms |
863316 KB |
Output is correct |
12 |
Correct |
359 ms |
863152 KB |
Output is correct |
13 |
Correct |
363 ms |
863172 KB |
Output is correct |
14 |
Correct |
342 ms |
863056 KB |
Output is correct |
15 |
Correct |
382 ms |
863108 KB |
Output is correct |
16 |
Correct |
356 ms |
863320 KB |
Output is correct |
17 |
Correct |
337 ms |
863192 KB |
Output is correct |
18 |
Correct |
336 ms |
863312 KB |
Output is correct |
19 |
Correct |
354 ms |
863104 KB |
Output is correct |
20 |
Correct |
337 ms |
863312 KB |
Output is correct |
21 |
Correct |
358 ms |
863316 KB |
Output is correct |
22 |
Correct |
344 ms |
863312 KB |
Output is correct |
23 |
Correct |
328 ms |
863176 KB |
Output is correct |
24 |
Runtime error |
2583 ms |
1048580 KB |
Execution killed with signal 9 |
25 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
356 ms |
863192 KB |
Output is correct |
2 |
Correct |
396 ms |
863060 KB |
Output is correct |
3 |
Correct |
397 ms |
863316 KB |
Output is correct |
4 |
Correct |
351 ms |
863224 KB |
Output is correct |
5 |
Correct |
361 ms |
863196 KB |
Output is correct |
6 |
Correct |
362 ms |
863240 KB |
Output is correct |
7 |
Correct |
337 ms |
863320 KB |
Output is correct |
8 |
Correct |
368 ms |
863188 KB |
Output is correct |
9 |
Correct |
362 ms |
863188 KB |
Output is correct |
10 |
Correct |
378 ms |
863316 KB |
Output is correct |
11 |
Correct |
324 ms |
863316 KB |
Output is correct |
12 |
Correct |
359 ms |
863152 KB |
Output is correct |
13 |
Correct |
363 ms |
863172 KB |
Output is correct |
14 |
Correct |
342 ms |
863056 KB |
Output is correct |
15 |
Correct |
382 ms |
863108 KB |
Output is correct |
16 |
Correct |
356 ms |
863320 KB |
Output is correct |
17 |
Correct |
337 ms |
863192 KB |
Output is correct |
18 |
Correct |
336 ms |
863312 KB |
Output is correct |
19 |
Correct |
354 ms |
863104 KB |
Output is correct |
20 |
Correct |
337 ms |
863312 KB |
Output is correct |
21 |
Correct |
358 ms |
863316 KB |
Output is correct |
22 |
Correct |
344 ms |
863312 KB |
Output is correct |
23 |
Correct |
328 ms |
863176 KB |
Output is correct |
24 |
Runtime error |
2583 ms |
1048580 KB |
Execution killed with signal 9 |
25 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
356 ms |
863192 KB |
Output is correct |
2 |
Correct |
396 ms |
863060 KB |
Output is correct |
3 |
Correct |
397 ms |
863316 KB |
Output is correct |
4 |
Correct |
351 ms |
863224 KB |
Output is correct |
5 |
Correct |
361 ms |
863196 KB |
Output is correct |
6 |
Correct |
362 ms |
863240 KB |
Output is correct |
7 |
Correct |
337 ms |
863320 KB |
Output is correct |
8 |
Correct |
368 ms |
863188 KB |
Output is correct |
9 |
Correct |
362 ms |
863188 KB |
Output is correct |
10 |
Correct |
378 ms |
863316 KB |
Output is correct |
11 |
Correct |
324 ms |
863316 KB |
Output is correct |
12 |
Correct |
359 ms |
863152 KB |
Output is correct |
13 |
Correct |
363 ms |
863172 KB |
Output is correct |
14 |
Correct |
342 ms |
863056 KB |
Output is correct |
15 |
Correct |
382 ms |
863108 KB |
Output is correct |
16 |
Correct |
356 ms |
863320 KB |
Output is correct |
17 |
Correct |
337 ms |
863192 KB |
Output is correct |
18 |
Correct |
336 ms |
863312 KB |
Output is correct |
19 |
Correct |
354 ms |
863104 KB |
Output is correct |
20 |
Correct |
337 ms |
863312 KB |
Output is correct |
21 |
Correct |
358 ms |
863316 KB |
Output is correct |
22 |
Correct |
344 ms |
863312 KB |
Output is correct |
23 |
Correct |
328 ms |
863176 KB |
Output is correct |
24 |
Runtime error |
2583 ms |
1048580 KB |
Execution killed with signal 9 |
25 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
395 ms |
863096 KB |
Output is correct |
2 |
Correct |
373 ms |
863056 KB |
Output is correct |
3 |
Correct |
329 ms |
863192 KB |
Output is correct |
4 |
Correct |
345 ms |
863312 KB |
Output is correct |
5 |
Correct |
325 ms |
863184 KB |
Output is correct |
6 |
Correct |
352 ms |
863132 KB |
Output is correct |
7 |
Correct |
381 ms |
863060 KB |
Output is correct |
8 |
Correct |
369 ms |
863060 KB |
Output is correct |
9 |
Correct |
390 ms |
863060 KB |
Output is correct |
10 |
Runtime error |
2704 ms |
1048576 KB |
Execution killed with signal 9 |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
360 ms |
863104 KB |
Output is correct |
2 |
Correct |
386 ms |
862948 KB |
Output is correct |
3 |
Correct |
325 ms |
863064 KB |
Output is correct |
4 |
Correct |
344 ms |
863568 KB |
Output is correct |
5 |
Correct |
355 ms |
863824 KB |
Output is correct |
6 |
Correct |
372 ms |
863256 KB |
Output is correct |
7 |
Correct |
340 ms |
863312 KB |
Output is correct |
8 |
Correct |
354 ms |
863316 KB |
Output is correct |
9 |
Correct |
439 ms |
868384 KB |
Output is correct |
10 |
Correct |
551 ms |
953936 KB |
Output is correct |
11 |
Correct |
427 ms |
863288 KB |
Output is correct |
12 |
Correct |
401 ms |
864084 KB |
Output is correct |
13 |
Correct |
703 ms |
974676 KB |
Output is correct |
14 |
Correct |
645 ms |
973648 KB |
Output is correct |
15 |
Correct |
915 ms |
992548 KB |
Output is correct |
16 |
Correct |
1843 ms |
1047448 KB |
Output is correct |
17 |
Correct |
865 ms |
1005140 KB |
Output is correct |
18 |
Correct |
629 ms |
979540 KB |
Output is correct |
19 |
Correct |
767 ms |
999188 KB |
Output is correct |
20 |
Correct |
754 ms |
999256 KB |
Output is correct |
21 |
Correct |
784 ms |
1004748 KB |
Output is correct |
22 |
Correct |
531 ms |
962896 KB |
Output is correct |
23 |
Correct |
356 ms |
863192 KB |
Output is correct |
24 |
Correct |
396 ms |
863060 KB |
Output is correct |
25 |
Correct |
397 ms |
863316 KB |
Output is correct |
26 |
Correct |
351 ms |
863224 KB |
Output is correct |
27 |
Correct |
361 ms |
863196 KB |
Output is correct |
28 |
Correct |
362 ms |
863240 KB |
Output is correct |
29 |
Correct |
337 ms |
863320 KB |
Output is correct |
30 |
Correct |
368 ms |
863188 KB |
Output is correct |
31 |
Correct |
362 ms |
863188 KB |
Output is correct |
32 |
Correct |
378 ms |
863316 KB |
Output is correct |
33 |
Correct |
324 ms |
863316 KB |
Output is correct |
34 |
Correct |
359 ms |
863152 KB |
Output is correct |
35 |
Correct |
363 ms |
863172 KB |
Output is correct |
36 |
Correct |
342 ms |
863056 KB |
Output is correct |
37 |
Correct |
382 ms |
863108 KB |
Output is correct |
38 |
Correct |
356 ms |
863320 KB |
Output is correct |
39 |
Correct |
337 ms |
863192 KB |
Output is correct |
40 |
Correct |
336 ms |
863312 KB |
Output is correct |
41 |
Correct |
354 ms |
863104 KB |
Output is correct |
42 |
Correct |
337 ms |
863312 KB |
Output is correct |
43 |
Correct |
358 ms |
863316 KB |
Output is correct |
44 |
Correct |
344 ms |
863312 KB |
Output is correct |
45 |
Correct |
328 ms |
863176 KB |
Output is correct |
46 |
Runtime error |
2583 ms |
1048580 KB |
Execution killed with signal 9 |
47 |
Halted |
0 ms |
0 KB |
- |