fork(3) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef vector<vector<int>> vvi;
  4. typedef vector<int> vi;
  5. typedef pair<vi, int> pvii;
  6. const int MAXN = 100005;
  7.  
  8. int N;
  9. vvi edges[2], levels[2];
  10. int ts[MAXN], label[2][MAXN], parent[2][MAXN];
  11. vi centroid[2];
  12.  
  13. int findCentroid(const int tID, const int u, const int p) {
  14.    int children = 0, curr;
  15.    for (auto& e : edges[tID][u]) {
  16.       if (e != p) {
  17.          curr = findCentroid(tID, e, u);
  18.          if (curr > (N >> 1))
  19.             break;
  20.          children += curr;
  21.       }//if
  22.    }//for
  23.    if (N - children - 1 <= (N >> 1))
  24.       centroid[tID].push_back(u);
  25.    return ts[u] = children + 1;
  26. }//findCentroid
  27.  
  28. int setLevels(const int tID, const int u, const int p, const int d) {
  29.    parent[tID][u] = p;
  30.    levels[tID][d].push_back(u);
  31.    int mx = d;
  32.    for (auto& e : edges[tID][u])
  33.       if (e != p)
  34.          mx = max(mx, setLevels(tID, e, u, d + 1));
  35.    return mx;
  36. }//setLevels
  37.  
  38. bool isoCheck(const int lvl) {
  39.    for (int it = lvl; it >= 0; it--) {
  40.       vector<pvii> order[2];
  41.       for (int i = 0; i < 2; i++) {
  42.          for (auto& u : levels[i][it]) {
  43.             order[i].push_back(pvii(vi(), u));
  44.             for (auto& e : edges[i][u])
  45.                if (e != parent[i][u])
  46.                   order[i].back().first.push_back(label[i][e]);
  47.          }//for
  48.       }//for
  49.       if ((int)order[0].size() != ((int)order[1].size()))
  50.          return 0;
  51.       for (int i = 0; i < 2; i++) {
  52.          for (int j = 0; j < (int)order[0].size(); j++)
  53.             sort(order[i][j].first.begin(), order[i][j].first.end());
  54.          sort(order[i].begin(), order[i].end());
  55.       }//for
  56.       int labelID = 0;
  57.       for (int i = 0; i < (int)order[0].size(); i++) {
  58.          if (order[0][i].first != order[1][i].first)
  59.             return 0;
  60.          if (i && order[0][i].first == order[0][i - 1].first) {
  61.             label[0][order[0][i].second] = label[1][order[1][i].second] = labelID;
  62.             continue;
  63.          }//if
  64.          label[0][order[0][i].second] = label[1][order[1][i].second] = ++labelID;
  65.       }//for
  66.    }//for
  67.    return 1;
  68. }//isoCheck
  69.  
  70. int main() {
  71.    int u, v;
  72.    int T;
  73.    scanf("%d", &T);
  74.    while (T--) {
  75.       scanf("%d", &N);
  76.       memset(ts, 0, sizeof(int) * (N + 2));
  77.       for (int i = 0; i < 2; i++) {
  78.          edges[i].assign(N + 5, vi());
  79.          levels[i].assign(N + 5, vi());
  80.          memset(label[i], 0, sizeof(int) * (N + 2));
  81.          memset(parent[i], 0, sizeof(int) * (N + 2));
  82.          centroid[i].clear();
  83.          for (int j = 0; j < N - 1; j++) {
  84.             scanf("%d %d", &u, &v);
  85.             edges[i][u].push_back(v);
  86.             edges[i][v].push_back(u);
  87.          }//for
  88.          findCentroid(i, edges[i][0].empty() ? 1 : 0, -1);
  89.       }//for
  90.       if (edges[0][0].empty())
  91.          N++;
  92.       if ((int)centroid[0].size() != (int)centroid[1].size()) {
  93.          puts("NO");
  94.          continue;
  95.       }//if
  96.       if ((int)centroid[0].size() == 2) {
  97.          for (int i = 0; i < 2; i++) {
  98.             for (int j = 0; j < 2; j++) {
  99.                edges[i][centroid[i][j]].erase(std::remove(edges[i][centroid[i][j]].begin(), edges[i][centroid[i][j]].end(), centroid[i][!j]), edges[i][centroid[i][j]].end());
  100.                edges[i][centroid[i][j]].push_back(N);
  101.                edges[i][N].push_back(centroid[i][j]);
  102.             }//for
  103.             centroid[i][0] = N;
  104.          }//for
  105.       }//if
  106.       int d[2];
  107.       for (int i = 0; i < 2; i++)
  108.          d[i] = setLevels(i, centroid[i][0], -1, 0);
  109.       if (d[0] != d[1]) {
  110.          puts("NO");
  111.          continue;
  112.       }//if
  113.       if (d[0] >= 0)
  114.          isoCheck(d[0] - 1) ? puts("YES") : puts("NO");
  115.    }//while
  116.    return 0;
  117. }//main
  118.  
Success #stdin #stdout 0s 17200KB
comments (?)
stdin
copy 
2
4
4 2
4 1
2 3
4 2
2 3
4 1
5
3 4
3 2
3 5
3 1
3 4
4 2
2 5
2 1
stdout
copy 
YES
NO
https://ideone.com/Qyvo1W
language:
C++14 (clang 8.0)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!