#include <bits/stdc++.h> #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); } using namespace std; const int N = 120005, LG = 18; const int M = N * 5; int n; vector<int> g[N]; int dep[N], fa[N], head[N], sz[N], in[N], tim, tour[N], out[N]; vector<int> st[N], ed[N]; int up[N][LG]; int lc[M], rc[M]; vector<int> adj[M]; int numNode; int build1(int l, int r) { int id = ++numNode; if(l == r) { for(int x : ed[tour[l]]) adj[id].emplace_back(x); return id; } int mid = (l + r) >> 1; lc[id] = build1(l, mid); rc[id] = build1(mid + 1, r); adj[id].emplace_back(lc[id]); adj[id].emplace_back(rc[id]); return id; } void update1(int k, int l, int r, int u, int v, int sus) { if(l > v || r < u) return; if(u <= l && r <= v) { adj[sus].emplace_back(k); return; } int mid = (l + r) >> 1; update1(lc[k], l, mid, u, v, sus); update1(rc[k], mid + 1, r, u, v, sus); } int build2(int l, int r) { int id = ++numNode; if(l == r) { for(int x : st[tour[l]]) adj[x].emplace_back(id); return id; } int mid = (l + r) >> 1; lc[id] = build2(l, mid); rc[id] = build2(mid + 1, r); adj[lc[id]].emplace_back(id); adj[rc[id]].emplace_back(id); return id; } void update2(int k, int l, int r, int u, int v, int sus) { if(l > v || r < u) return; if(u <= l && r <= v) { adj[k].emplace_back(sus); return; } int mid = (l + r) >> 1; update2(lc[k], l, mid, u, v, sus); update2(rc[k], mid + 1, r, u, v, sus); } void pdfs(int u) { sz[u] = 1; for(int v : g[u]) if(v != fa[u]) { dep[v] = dep[u] + 1; fa[v] = u; up[v][0] = u; for(int i = 1; i < LG; ++i) up[v][i] = up[up[v][i - 1]][i - 1]; pdfs(v); sz[u] += sz[v]; } } void hld(int u, int hd) { head[u] = hd; in[u] = ++tim; tour[tim] = u; int hc = -1; for(int v : g[u]) if(v != fa[u]) { if(hc == -1 || sz[v] > sz[hc]) hc = v; } if(hc != -1) hld(hc, hd); for(int v : g[u]) if(v != fa[u] && v != hc) hld(v, v); out[u] = tim; } bool isFa(int p, int u) { return in[p] < in[u] && in[u] <= out[p]; } int r1, r2; void add1(int i, int u, int v) { while(head[u] != head[v]) { if(dep[head[u]] < dep[head[v]]) swap(u, v); update1(r1, 1, n, in[head[u]], in[u], i); u = fa[head[u]]; } if(dep[u] > dep[v]) swap(u, v); update1(r1, 1, n, in[u], in[v], i); } void add2(int i, int u, int v) { while(head[u] != head[v]) { if(dep[head[u]] < dep[head[v]]) swap(u, v); update2(r2, 1, n, in[head[u]], in[u], i); u = fa[head[u]]; } if(dep[u] > dep[v]) swap(u, v); update2(r2, 1, n, in[u], in[v], i); } int jump(int u, int k) { for(int i = LG - 1; i >= 0; --i) if(k >> i & 1) u = up[u][i]; return u; } void upd1(int i, int u, int v) { if(isFa(v, u)) { add1(i, u, jump(u, dep[u] - dep[v] - 1)); } else { add1(i, u, fa[v]); } } void upd2(int i, int u, int v) { if(isFa(u, v)) { add2(i, jump(v, dep[v] - dep[u] - 1), v); } else add2(i, fa[u], v); } pair<int, int> Q[N]; int vis[M]; bool cyc; void dfs(int u) { // cout << u << '\n'; vis[u] = 1; for(int v : adj[u]) { if(vis[v] == 1) { cyc = true; } if(vis[v] == 0) dfs(v); } vis[u] = 2; } void solve() { cin >> n; for(int i = 1; i < n; ++i) { int u, v; cin >> u >> v; g[u].emplace_back(v); g[v].emplace_back(u); } pdfs(1); hld(1, 1); int m; cin >> m; numNode = m; for(int i = 1; i <= m; ++i) { int s, t; cin >> s >> t; Q[i] = make_pair(s, t); st[s].emplace_back(i); ed[t].emplace_back(i); } r1 = build1(1, n); r2 = build2(1, n); for(int i = 1; i <= m; ++i) { upd1(i, Q[i].first, Q[i].second); upd2(i, Q[i].first, Q[i].second); } for(int i = 1; i <= numNode; ++i) { if(!vis[i]) dfs(i); } cout << (cyc ? "No" : "Yes") << '\n'; cyc = false; tim = 0; for(int i = 1; i <= numNode; ++i) { adj[i].clear(); vis[i] = 0; } for(int i = 1; i <= n; ++i) { for(int j = 0; j < LG; ++j) up[i][j] = 0; g[i].clear(); st[i].clear(); ed[i].clear(); } numNode = 0; } int main() { ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0); file("A") else file("task"); int tc; cin >> tc; for(int _ = 1; _ <= tc; ++_) solve(); return 0; }

jail.cpp: In function 'int main()':
jail.cpp:2:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jail.cpp:188:5: note: in expansion of macro 'file'
  188 |     file("A") else file("task");
      |     ^~~~
jail.cpp:2:91: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
jail.cpp:188:5: note: in expansion of macro 'file'
  188 |     file("A") else file("task");
      |     ^~~~
jail.cpp:2:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jail.cpp:188:20: note: in expansion of macro 'file'
  188 |     file("A") else file("task");
      |                    ^~~~
jail.cpp:2:91: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
jail.cpp:188:20: note: in expansion of macro 'file'
  188 |     file("A") else file("task");
      |                    ^~~~