Source Code
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define all(v) v.begin(), v.end()
#define pb push_back    
#define sz(x) (int)(x).size()
const int N = 1e5 + 5;
void solve() {
    int n;
    cin >> n;
    map<char, int> m;
    m['U'] = 0;
    m['D'] = 1;
    m['L'] = 2;
    m['R'] = 3;
    m['&'] = 13;
    vector<vi> deg(n + 10, vi(15));
    //dp(n + 4, vi(15, 1)), vis(n + 4, vi(15, 0));
    vi can(n + 5, 1), bad(n + 5, 1);
    vector<vector<pii>> g(n + 5);
    for(int i = 0; i < n - 1; ++i){
        int u, v;
        char c;
        cin >> u >> v >> c;
        g[u].pb({v, c});
        g[v].pb({u, c});
        ++deg[u][m[c]];
        ++deg[v][m[c]];
        if(deg[u][m[c]] >= 2)   
            can[u] = 0;
        if(deg[v][m[c]] >= 2)   
            can[v] = 0;
        if(deg[u][m[c]] >= 3)   
            bad[u] = 0;
        if(deg[v][m[c]] >= 3)   
            bad[v] = 0;
    }
    auto check = [&](char c, char d){
        return (c == 'L' && d == 'R') || (c == 'R' && d == 'L')
                || (c == 'D' && d == 'U') || (c == 'U' && d == 'D');
    };
    int src;
    function<int(int, char, int)> dfs = [&](int u, char d, int par) -> int { 
        int j = m[d];
        if(!bad[u])
            return 0;
        int ret = 1;
        vi cdeg(4);
        for(int i = 0; i < 4; ++i){
            cdeg[i] = deg[u][i] - (j == i);
            ret &= (cdeg[i] < 2);
        }
        if(!ret)
            return 0;
        for(auto [v, c] : g[u]){
            if(check(c, d)){
                ret = 0;
            }else if(par != v){
                ret &= dfs(v, c, u);
            }
        }
        return ret;
    };
    vi ans;
    for(int i = 1; i <= n; ++i){
        bool ok = 1;
        if(can[i]){
            src = i;
            ok &= dfs(i, '&', -1);
        }else{
            ok = 0;
        }
        if(ok)
            ans.pb(i);
    }
    for(int x : ans)
        cout << x << ' ';
}
int main() {
    // cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    cin >> t;
    // scanf("%d",&t);
    while(t--)
        solve(), cout << '\n';
}
Copy
Flow Sources I noomaK
GNU G++17
2100 ms
13.1 MB
Time Limit Exceeded