제출 #1347839

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

using namespace std;

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

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

  // hld
  vector<int> subtree_sz(n);
  auto dfs_sz = [&](auto &&self, int u, int p) -> void {
    subtree_sz[u] = 1;
    if (adj[u].size() > 1 && adj[u][0] == p) {
      swap(adj[u][0], adj[u][1]);
    }
    for (int i = 0; i < adj[u].size(); ++i) {
      if (adj[u][i] == p) {
        continue;
      }
      self(self, adj[u][i], u);
      subtree_sz[u] += subtree_sz[i];
      if (subtree_sz[adj[u][i]] > subtree_sz[adj[u][0]]) {
        swap(adj[u][i], adj[u][0]);
      }
    }
  };
  dfs_sz(dfs_sz, 0, -1);
  vector<int> par(n), up(n), tin(n);
  int timer = 0;
  auto dfs_hld = [&](auto &&self, int u, int p) -> void {
    tin[u] = timer++;
    for (int &i : adj[u]) {
      if (i == p) {
        continue;
      }
      par[i] = u;
      up[i] = i == adj[u][0] ? up[u] : i;
      self(self, i, u);
    }
  };
  dfs_hld(dfs_hld, 0, -1);
  auto path_from = [&](int u, int v) {
    vector<pair<int, int>> ans;
    while (u != v) {
      if (tin[u] < tin[v]) {
        swap(u, v);
      }
      if (up[u] == up[v]) {
        ans.push_back({tin[v], tin[u]});
        break;
      }
      ans.push_back({tin[up[u]], tin[u]});
      u = par[up[u]];
    }
    ans.push_back({tin[v], tin[v]});
    return ans;
  };

  // add edge i => [x, y]
  // so i -> x, i -> x+1, i -> x+2, ..., i -> y
  vector<vector<int>> nadj(m + 4 * n);
  // m + x => first layer
  auto first = [&](int u) { return m + u; };
  // m+2*n + x => second layer
  auto second = [&](int u) { return m + 2 * n + u; };
  vector<int> with_tin(n);
  for (int i = 0; i < n; ++i) {
    with_tin[tin[i]] = i;
  }
  for (int i = 0; i < n; ++i) {
    if (e[with_tin[i]] != -1) {
      nadj[first(i + n)].push_back(e[with_tin[i]]);
    }
    if (i != 0) {
      nadj[first(i)].push_back(first(2 * i));
      nadj[first(i)].push_back(first(2 * i + 1));
    }
  }
  auto add_edge_onetomany = [&](int u, int l, int r) { // u => [l, r]
    auto add = [&](int v) {
      nadj[u].push_back(first(v));
    };
    for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1)
        add(l++);
      if (r & 1)
        add(--r);
    }
  };

  // add edge [x, y] => i
  // so x -> i, x+1 -> i, x+2 -> i, x+3 -> i, ..., y -> i
  for (int i = 0; i < n; ++i) {
    if (s[with_tin[i]] != -1) {
      nadj[s[with_tin[i]]].push_back(second(i + n));
    }
    if (i != 0) {
      nadj[second(2 * i)].push_back(second(i));
      nadj[second(2 * i + 1)].push_back(second(i));
    }
  }
  auto add_edge_manytoone = [&](int l, int r, int u) { // [l, r] => u
    auto add = [&](int v) {
      nadj[second(v)].push_back(u);
    };
    for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1)
        add(l++);
      if (r & 1)
        add(--r);
    }
  };

  for (int i = 0; i < m; ++i) {
    int u = sts[i], v = ens[i];
    vector<pair<int, int>> ints = path_from(u, v);
    // i -> [u, v-1]
    for (auto [l, r] : ints) {
      l += l == tin[v];
      r -= r == tin[v];
      add_edge_onetomany(i, l, r);
    }
    // [u+1, v] -> i
    for (auto [l, r] : ints) {
      l += l == tin[u];
      r -= r == tin[u];
      add_edge_manytoone(l, r, i);
    }
  }

  int cycle_there = 0;
  vector<bool> vis(m + 4 * n), stk(m + 4 * n);
  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 + 4 * n);
  for (int i = 0; i < m + 4 * n; ++i) {
    sort(nadj[i].begin(), nadj[i].end());
    nadj[i].erase(unique(nadj[i].begin(), nadj[i].end()), nadj[i].end());
    for (auto &u : nadj[i]) {
      indeg[u]++;
    }
  }
  for (int i = 0; i < m + 4 * n; ++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...