Submission #1479275

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <list>

using namespace std;

const int MaxN = 2e5 + 5;

vector<int> gb[MaxN], gr[MaxN];

int dep[MaxN], fa[MaxN], d[MaxN];
bool safe[MaxN], vis[MaxN];

int main() {
  ios_base::sync_with_stdio(false);
  int n, sx, sy;
  cin >> n >> sx >> sy;
  for (int i = 1; i < n; ++i) {
    int x, y;
    cin >> x >> y;
    gr[x].emplace_back(y);
    gr[y].emplace_back(x);
  }
  for (int i = 1; i < n; ++i) {
    int x, y;
    cin >> x >> y;
    gb[x].emplace_back(y);
    gb[y].emplace_back(x);
  }
  list<int> Q;
  Q.emplace_back(sy);
  fa[sy] = -1;
  vis[sy] = true;
  while (!Q.empty()) {
    int k = Q.front();
    for (int x : gb[k]) {
      if (!vis[x]) {
        Q.emplace_back(x);
        vis[x] = true;
        dep[x] = dep[k] + 1;
        fa[x] = k;
      }
    }
    Q.pop_front();
  }
  for (int i = 1; i <= n; ++i) {
    for (int k : gr[i]) {
      if (![](int x, int y) -> bool {
        return fa[x] == fa[y] || fa[x] == y || x == fa[y] || fa[fa[x]] == y || x == fa[fa[y]];
      } (i, k)) {
        safe[i] = safe[k] = true;
      }
    }
  }
  if (safe[sx]) {
    cout << -1 << endl;
    return 0;
  }
  int ans = 0;
  memset(d, 0xff, sizeof d);
  d[sx] = 0;
  Q.emplace_back(sx);
  while (!Q.empty()) {
    int k = Q.front();
    Q.pop_front();
    if (d[k] >= dep[k]) {
      continue;
    }
    if (safe[k]) {
      cout << -1 << endl;
      return 0;
    }
    ans = max(ans, dep[k] * 2);
    for (int x : gr[k]) {
      if (vis[x] && d[k] + 1 < dep[x] && [](int x, int y) -> bool {
        return fa[x] == fa[y] || fa[x] == y || x == fa[y] || fa[fa[x]] == y || x == fa[fa[y]];
        } (k, x)) {
        d[x] = d[k] + 1;
        vis[x] = false;
        Q.emplace_back(x);
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Submission Info

Judge Result