CF1827E Bus Routes

CF1827E Bus Routes

所有点两两可达当且仅当所有叶子两两可达，而两个叶子可达当且仅当以 T_x\cup T_y \neq \varnothing，其中 T_x 表示以 x 为一端的所有路径的并，即 x 和以 x 为一端的路径的所有另一端形成的虚树。

设 S_x 表示 x 和以 x 为一端的路径的所有另一端形成的点集，则相当于查询是否存在一条边，使得 S_x 和 S_y 全部分别在边的两侧。

设 c_{i, j} 表示以 i 为根的子树内有多少个属于 S_j 的点，可以 dsu on tree 统计，同时维护所有 c_{i, j} = 0 和 c_{i, j} = |S_j| 的 j 的集合即可。如果用 set 维护，则时间复杂度 \mathcal{O}(n\log ^ 2 n)，空间复杂度线性，会 TLE。因为要求加元素删元素查询任意一个元素，用 vector + 懒惰删除维护，时空复杂度均为 \mathcal{O}(n\log n)。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ull = unsigned long long;

constexpr int mod = 998244353;
void addt(int &x, int y) {x += y, x >= mod && (x -= mod);}
int add(int x, int y) {return x += y, x >= mod && (x -= mod), x;}
int ksm(int a, int b) {
  int s = 1;
  while(b) {
    if(b & 1) s = 1ll * s * a % mod;
    a = 1ll * a * a % mod, b >>= 1;
  }
  return s;
}

bool Mbe;
constexpr int N = 5e5 + 5;
constexpr int K = N << 5;

int n, m, cnt[N];
bool leaf[N];
vector<int> e[N], f[N];

int dn, dfn[N], rev[N], sz[N], son[N];
void dfs1(int id, int ff) {
  son[id] = 0;
  sz[id] = 1;
  rev[dfn[id] = ++dn] = id;
  for(int it : e[id]) {
    if(it == ff) continue;
    dfs1(it, id), sz[id] += sz[it];
    if(sz[son[id]] < sz[it]) son[id] = it;
  }
}

int x, y, buc[N], de[N], df[N];
int E, ept[K], F, ful[K];
void ad(int x, int v) {
  for(int it : f[x]) {
    if(!leaf[it]) continue;
    if(buc[it] == 0) de[it]++;
    if(buc[it] == cnt[it]) df[it]++;
    buc[it] += v;
    if(buc[it] == 0) ept[++E] = it;
    if(buc[it] == cnt[it]) ful[++F] = it;
  }
}

void clear(int x, int v) {
  int l = dfn[x], r = l + sz[x] - 1;
  for(int p = l; p <= r; p++) ad(rev[p], v);
}
void dfs(int id, int ff) {
  for(int it : e[id]) {
    if(it == ff || it == son[id]) continue;
    dfs(it, id), clear(it, -1);
  }
  if(son[id]) dfs(son[id], id);
  ad(id, 1);
  for(int it : e[id]) {
    if(it == ff || it == son[id]) continue;
    clear(it, 1);
  }
  while(E && de[ept[E]]) de[ept[E--]]--;
  while(F && df[ful[F]]) df[ful[F--]]--;
  if(E && F) x = ept[E], y = ful[F];
}

void solve() {
  cin >> n >> m;
  for(int i = 1; i <= n; i++) {
    e[i].clear();
    f[i].clear();
    cnt[i] = buc[i] = de[i] = df[i] = 0;
  }
  for(int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    e[u].push_back(v);
    e[v].push_back(u);
  }
  dn = 0, dfs1(1, 0);
  for(int i = 1; i <= n; i++) {
    leaf[i] = e[i].size() == 1;
  }
  for(int i = 1; i <= m; i++) {
    int x, y;
    cin >> x >> y;
    cnt[x]++, cnt[y]++;
    if(leaf[x]) f[y].push_back(x);
    if(leaf[y]) f[x].push_back(y);
  }
  for(int i = 1; i <= n; i++) {
    if(!leaf[i] || cnt[i]) continue;
    cout << "NO\n";
    cout << i << " " << 1 + (i == 1) << "\n";
    return;
  }
  E = F = 0;
  for(int i = 1; i <= n; i++) {
    if(!leaf[i]) continue;
    cnt[i]++, f[i].push_back(i);
    ept[++E] = i;
  }
  x = y = -1, dfs(1, 0);
  if(x == -1) cout << "YES\n";
  else cout << "NO\n" << x << " " << y << "\n";
}

bool Med;
int main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int T = 1;
  cin >> T;
  while(T--) solve();
  cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
  return 0;
}