제출 #1347739

#제출 시각아이디문제언어결과실행 시간메모리
1347739avighnaJail (JOI22_jail)C++20
49 / 100
5093 ms22960 KiB
#include <bits/stdc++.h>

using namespace std;

void solve() {
  int n;
  cin >> n;
  vector<vector<int>> adj(n + 1);
  for (int i = 0, u, v; i < n - 1; ++i) {
    cin >> u >> v;
    adj[u].push_back(v), adj[v].push_back(u);
  }

  int m;
  cin >> m;
  vector<int> s(n + 1, -1), e(n + 1, -1), sts, ens;
  for (int i = 0, x, y; i < m; ++i) {
    cin >> x >> y;
    s[x] = i, e[y] = i;
    sts.push_back(x), ens.push_back(y);
  }

  vector<int> par(n + 1);
  int v = -1, found = 0;
  auto dfs = [&](auto &&self, int u, int p) {
    found |= u == v;
    if (found) {
      return;
    }
    for (int &i : adj[u]) {
      if (i == p) {
        continue;
      }
      if (found) {
        return;
      }
      par[i] = u;
      self(self, i, u);
    }
  };

  vector<set<int>> nadj(m);
  for (int i = 0; i < m; ++i) {
    found = 0;
    v = ens[i];
    dfs(dfs, sts[i], 0);
    auto check = [&](int u) {
      if (s[u] != -1 && s[u] != i) {
        nadj[s[u]].insert(i);
      }
      if (e[u] != -1 && e[u] != i) {
        nadj[i].insert(e[u]);
      }
    };
    set<int> st;
    for (int u = par[v]; u != sts[i]; u = par[u]) {
      st.insert(u);
    }
    st.insert(v), st.insert(sts[i]);
    for (auto &i : st) {
      check(i);
    }
  }

  int cycle_there = 0;
  vector<bool> vis(m), stk(m);
  auto dfs2 = [&](auto &&self, int u) {
    cycle_there |= stk[u];
    if (vis[u]) {
      return;
    }
    vis[u] = stk[u] = true;
    for (auto &i : nadj[u]) {
      self(self, i);
    }
    stk[u] = false;
  };

  deque<int> dq;
  vector<int> indeg(m);
  for (int i = 0; i < m; ++i) {
    for (auto &u : nadj[i]) {
      indeg[u]++;
    }
  }
  for (int i = 0; i < m; ++i) {
    if (indeg[i] == 0) {
      dq.push_front(i);
    } else {
      dq.push_back(i);
    }
  }
  for (auto &i : dq) {
    if (!vis[i]) {
      dfs2(dfs2, i);
    }
  }
  cout << (cycle_there ? "No" : "Yes") << '\n';
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);

  int t;
  cin >> t;
  while (t--) {
    solve();
  }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...