#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 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;
int n, m;
vvi adj;
vi depth;
vi parent;
vii inOut;
int counter;
void dfs(int node, int p, int d) {
depth[node] = d;
lift[0][node] = p;
inOut[node].first = counter++;
for (int child : adj[node]) {
if (child == p) continue;
parent[child] = node;
dfs(child, node, d + 1);
}
inOut[node].second = counter++;
}
constexpr int POW = 20;
vi lift[POW];
bool isAncestor(int a, int b) {
return inOut[a].first <= inOut[b].first && inOut[b].first <= inOut[a].second;
}
bool isBetween(int node, int a, int b) {
return isAncestor(a, node) && isAncestor(node, b);
}
int getLCA(int a, int b) {
if (depth[a] < depth[b]) swap(a, b);
int todo = depth[a] - depth[b];
loop(pow, POW) {
if (todo & (1 << pow)) {
a = lift[pow][a];
}
}
if (a == b) return a;
for (int pow = POW - 1; pow >= 0; pow--) {
if (lift[pow][a] == lift[pow][a]) continue;
a = lift[pow][a];
b = lift[pow][b];
}
return lift[0][a];
}
bool isOnSimplePath(int node, int a, int b) {
int lca = getLCA(a, b);
bool result = isBetween(node, lca, a) || isBetween(node, lca, b);
return result;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
/*
*/
int q;
cin >> q;
while (q--) {
cin >> n;
counter = 0;
adj = vvi(n);
depth = vi(n);
parent = vi(n);
inOut = vii(n);
loop(i, n - 1) {
int a, b;
cin >> a >> b;
a--; b--;
adj[a].push_back(b);
adj[b].push_back(a);
}
loop(i, POW) {
lift[i] = vi(n);
}
dfs(0, 0, 0);
for (int pow = 1; pow < POW; pow++) {
loop(j, n) {
int next = lift[pow - 1][j];
lift[pow][j] = lift[pow - 1][next];
}
}
vii routes;
cin >> m;
loop(i, m) {
int s, t;
cin >> s >> t;
s--; t--;
routes.push_back({s, t});
}
vi inDegree(m);
vector<set<int>> out(m);
loop(i, m) {
auto [s1, t1] = routes[i];
loop(j, m) {
auto [s2, t2] = routes[j];
if (i == j) continue;
if (isOnSimplePath(t2, s1, t1)) {
if (!out[i].count(j)) {
out[i].insert(j);
inDegree[j]++;
}
}
if (isOnSimplePath(s2, s1, t1)) {
if (!out[j].count(i)) {
out[j].insert(i);
inDegree[i]++;
}
}
}
}
stack<int> startingPoints;
loop(i, m) {
if (inDegree[i] == 0) startingPoints.push(i);
}
int count = 0;
vb vis(m);
while (startingPoints.size()) {
int node = startingPoints.top();
startingPoints.pop();
if (vis[node]) continue;
vis[node] = true;
count++;
for (int child : out[node]) {
inDegree[child]--;
if (inDegree[child] == 0) startingPoints.push(child);
}
}
if (count == m) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
}
return 0;
}
Compilation message
jail.cpp: In function 'void dfs(int, int, int)':
jail.cpp:40:5: error: 'lift' was not declared in this scope
40 | lift[0][node] = p;
| ^~~~
