This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
//#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef uint64_t u64;
typedef int64_t i64;
int n, m;
vvi adj;
vi depth;
vi parent;
void dfs(int node, int p, int d) {
depth[node] = d;
for (int child : adj[node]) {
if (child == p) continue;
parent[child] = node;
dfs(child, node, d + 1);
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
/*
1
7
1 2
2 3
3 4
4 5
5 6
6 7
3
1 3
4 2
2 5
*/
/*
1
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
3
1 4
2 5
3 6
*/
int q;
cin >> q;
constexpr int POW = 20;
while (q--) {
cin >> n;
adj = vvi(n);
depth = vi(n);
parent = vi(n);
loop(i, n - 1) {
int a, b;
cin >> a >> b;
a--; b--;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(0, -1, 0);
vi lift[POW] = {};
vvi endPointLift[POW] = {};
loop(i, POW) {
lift[i] = vi(n);
endPointLift[i] = vvi(n);
}
loop(i, n) lift[0][i] = parent[i];
vii routes;
cin >> m;
loop(i, m) {
int s, t;
cin >> s >> t;
s--; t--;
routes.push_back({s, t});
endPointLift[0][t].push_back(i);
}
// for (int i = 1; i < POW; i++) {
// loop(j, n) {
// endPointLift[i][j] = endPointLift[i - 1][j];
// int next = lift[i - 1][j];
// lift[i][j] = lift[i - 1][next];
// //if (next == 0) continue;
// for (int x : endPointLift[i - 1][next]) {
// endPointLift[i][j].push_back(x);
// }
// }
// }
// vi inDegree(n);
// vector<set<int>> out(n);
// loop(i, m) {
// auto [s, t] = routes[i];
// vi endPointsOnRoute;
// if (depth[s] < depth[t]) swap(s, t);
// int todo = depth[s] - depth[t];
// loop(j, POW) {
// if (todo & (1 << j)) {
// for (int x : endPointLift[j][s]) endPointsOnRoute.push_back(x);
// s = lift[j][s];
// }
// }
// for (int j = POW - 1; j >= 0; j--) {
// if (lift[j][s] == lift[j][t]) continue;
// for (int x : endPointLift[j][s]) endPointsOnRoute.push_back(x);
// for (int x : endPointLift[j][t]) endPointsOnRoute.push_back(x);
// s = lift[j][s];
// t = lift[j][t];
// }
// if (s == t) {
// for (int x : endPointLift[0][s]) endPointsOnRoute.push_back(x);
// }
// else {
// for (int x : endPointLift[1][s]) endPointsOnRoute.push_back(x);
// for (int x : endPointLift[0][t]) endPointsOnRoute.push_back(x);
// }
// cerr << "I = " << i << ": ";
// for (int x : endPointsOnRoute) {
// if (x == i) continue;
// cerr << x << ' ';
// inDegree[x]++;
// out[i].insert(x);
// }
// cerr << endl;
// }
// stack<int> startingPoints;
// loop(i, m) {
// if (inDegree[i] == 0) startingPoints.push(i);
// }
// int count = 0;
// while (startingPoints.size()) {
// int node = startingPoints.top();
// startingPoints.pop();
// count++;
// for (int child : out[node]) {
// inDegree[child]--;
// if (inDegree[child] == 0) startingPoints.push(child);
// }
// }
bool success = true;
sort(all(routes));
int prev = 0;
for (auto [s, t] : routes) {
if (t < prev) {
success = false;
}
prev = t;
}
if (/*count == m*/success) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
}
return 0;
}
# | 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... |