Submission #1365321

#TimeUsernameProblemLanguageResultExecution timeMemory
1365321behradJail (JOI22_jail)C++20
100 / 100
522 ms296772 KiB
#ifdef LOCAL
#include "/home/bgopc/template/pch.hpp"
#endif
#include <bits/stdc++.h>
using namespace std;
// * No One Dies a Virgin, Life Fucks Us All
typedef long long ll;
#define nl '\n'
#define ff first
#define ss second
#define pb push_back
#define sik(x) {cout << x << nl; return;}
constexpr ll maxn = 1.2e5+5, mod = 1e9 + 7, inf = 1e17, SQ = 450, LG = 19, maxN = 40 * maxn;
typedef pair<int, int> pii;

int n, m, s[maxn], t[maxn], sid[maxn], tid[maxn], up[maxn][LG], h[maxn], N, ind[maxN];
vector<int> g[maxn], adj[maxN];

inline int ID1(int v, int k) { return m + k * n + v; }
inline int ID2(int v, int k) { return ID1(v, k + LG); }

void dfs(int v, int p = 0) {
  up[v][0] = p;
  for (int i = 1 ; i < LG ; i ++) up[v][i] = up[up[v][i - 1]][i - 1];
  for (int u : g[v]) if (u != p) {
    h[u] = h[v] + 1;
    dfs(u, v);
  }
}

inline int Kth(int v, int k) {
  for (int i = 0 ; i < LG ; i ++) if (k >> i & 1) v = up[v][i];
  return v;
}

inline int LCA(int u, int v) {
  if (h[u] > h[v]) swap(u, v);
  v = Kth(v, h[v] - h[u]);
  if (u == v) return u;
  for (int i = LG - 1 ; i >= 0 ; i --) {
    if (up[u][i] != up[v][i]) {
      u = up[u][i];
      v = up[v][i];
    }
  }
  return up[u][0];
}

inline int getC(int v, int u) {
  return Kth(u, h[u] - h[v] - 1);
}

inline void addE(int u, int v) {
  adj[u].pb(v);
  ++ ind[v];
}

void add1(int u, int v, int x) {
  if (h[u] < h[v]) return ;
  int d = h[u] - h[v] + 1;
  int k = 31 - __builtin_clz(d);
  int w = Kth(u, d - (1 << k));
  addE(ID1(u, k), x);
  addE(ID1(w, k), x);
}

void add2(int x, int u, int v) {
  if (h[u] < h[v]) return ;
  int d = h[u] - h[v] + 1;
  int k = 31 - __builtin_clz(d);
  int w = Kth(u, d - (1 << k));
  addE(x, ID2(u, k));
  addE(x, ID2(w, k));
}

void run() {
  cin >> n;
  for (int i = 1 ; i <= n ; i ++) {
    g[i].clear();
    sid[i] = tid[i] = 0;
  }
  for (int i = 1 , u ,v ; i < n ; i ++) {
    cin >> u >> v;
    g[u].pb(v);
    g[v].pb(u);
  }
  cin >> m;
  for (int i = 1 ; i <= m ; i ++) {
    cin >> s[i] >> t[i];
    sid[s[i]] = i;
    tid[t[i]] = i;
  }

  dfs(1);

  N = m + 2 * LG * n;
  for (int i = 1 ; i <= N ; i ++) adj[i].clear(), ind[i] = 0;

  for (int i = 1 ; i <= n ; i ++) {
    if (sid[i]) addE(sid[i], ID1(i, 0));
    if (tid[i]) addE(ID2(i, 0), tid[i]);
  }

  for (int j = 1 ; j < LG ; j ++) {
    for (int v = 1 ; v <= n ; v ++) {
      int u = up[v][j - 1];
      addE(ID1(v, j - 1), ID1(v, j));
      addE(ID2(v, j), ID2(v, j - 1));
      if (u) {
        addE(ID1(u, j - 1), ID1(v, j));
        addE(ID2(v, j), ID2(u, j - 1));
      }
    }
  }

  for (int i = 1 ; i <= m ; i ++) {
    int lca = LCA(s[i], t[i]);

    if (t[i] != lca) {
      if (s[i] == lca) add1(t[i], getC(lca, t[i]), i);
      else add1(t[i], lca, i);
    }
    if (s[i] != lca) add1(up[s[i]][0], lca, i);

    if (s[i] != lca) {
      if (t[i] == lca) add2(i, s[i], getC(lca, s[i]));
      else add2(i, s[i], lca);
    }
    if (t[i] != lca) add2(i, up[t[i]][0], lca);
  }

  queue<int> q;
  for (int i = 1 ; i <= N ; i ++) if (!ind[i]) q.push(i);

  int vis = 0;
  while (q.size()) {
    int v = q.front(); q.pop();
    ++ vis;

    for (int u : adj[v]) {
      if (! -- ind[u]) q.push(u);
    }
  }
  cout << (vis == N ? "Yes\n" : "No\n");
}

int32_t main() {
  cin.tie(0)->sync_with_stdio(0); 
  int tt = 1;
  cin >> tt;
  while (tt --) run();
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...