Source Code
// FUCK JAVA
#include "bits/stdc++.h"
using namespace std;

struct Edge {
  const int to;
  const int dir;

  Edge(int to, int dir)
      : to(to), dir(dir) {}
};

inline int mapDirToInt(char dir) {
  switch (dir) {
    case 'L': return 0;
    case 'R': return 1;
    case 'U': return 2;
    case 'D': return 3;
    default: assert(false);
  }
}

const int N = 1e5;

vector<Edge> adj[N];
bitset<N> down;
bitset<N> up;
bitset<N> can;
vector<int> visDir[N];

inline bool isGoodBranch(const Edge &e) {
  return down[e.to] && !visDir[e.to][e.dir ^ 1];
};

void dfsDown(int node, int parent) {
  down[node] = true;
  for (auto &edge : adj[node]) {
    auto [child, dir] = edge;
    if (child == parent) {
      continue;
    }
    if (visDir[node][dir]) {
      down[node] = false;
    } else {
      visDir[node][dir] = true;
    }
    dfsDown(child, node);
    down[node] = down[node] && isGoodBranch(edge);
  }
};

void dfsUp(int node, int parent) {
  vector<int> dirFreq(4, 0);
  int cntGoodBranches = 0;
  int cntChildren = 0;
  for (auto &edge : adj[node]) {
    auto [child, dir] = edge;
    if (child != parent) {
      ++cntChildren;
      if (isGoodBranch(edge)) {
        ++cntGoodBranches;
      }
    }
    ++dirFreq[dir];
  }
  for (auto &edge : adj[node]) {
    auto [child, dir] = edge;
    if (child == parent) {
      continue;
    }
    --dirFreq[dir];
    if (isGoodBranch(edge)) {
      --cntGoodBranches;
    }
    bool hasDuplicates = false;
    if (*max_element(dirFreq.begin(), dirFreq.end()) > 1) {
      hasDuplicates = true;
    }
    up[child] = up[node] && !hasDuplicates && cntGoodBranches == cntChildren - 1 && dirFreq[dir ^ 1] == 0;
    dfsUp(child, node);
    if (isGoodBranch(edge)) {
      ++cntGoodBranches;
    }
    ++dirFreq[dir];
  }
};

void solve() {
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    adj[i].clear();
  }
  down.reset();
  up.reset();
  can.reset();
  for (int i = 0; i < n - 1; ++i) {
    int a, b;
    char c;
    cin >> a >> b >> c;
    --a;
    --b;
    adj[a].emplace_back(b, mapDirToInt(c));
    adj[b].emplace_back(a, mapDirToInt(c));
  }
  for (int i = 0; i < n; ++i) {
    visDir[i] = vector<int>(4);
  }
  dfsDown(0, -1);
  up[0] = true;
  dfsUp(0, -1);
  for (int node = 0; node < n; ++node) {
    vector<int> dirFreq(4, 0);
    for (auto edge : adj[node]) {
      ++dirFreq[edge.dir];
    }
    can[node] = down[node] && up[node] && (*max_element(dirFreq.begin(), dirFreq.end()) <= 1);
  }
  for (int node = 0; node < n; ++node) {
    if (can[node]) {
      cout << node + 1 << ' ';
    }
  }
  cout << '\n';
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}
Copy
Flow Sources I abdulrahman_aj
GNU G++17
1854 ms
25.8 MB
Accepted