Astralis session I

#include <bits/stdc++.h>

using namespace std;
#define ll long long

void dfs(vector<vector<int>>& g, int u, int from, vector<int>& acc, bool& start, pair<int, int>& edge, vector<bool>& visited) {

    
    if (visited[u]) return;
    visited[u] = true;
    
    int a = 1;
    for (auto &v : g[u]) {
        dfs(g, v, u, acc, start, edge, visited);
        a += acc[v];    
    }
    
    acc[u] = a;

    // cout << u << " " << acc[u] << endl;

    if (!start) {
        int n = g.size();
        if (n == 2*acc[u]) {
            start = true;
            edge = make_pair(u, from);
        }
    }

}

void dfsfill(vector<vector<int>>& g, int u, int color, pair<int, int>& banned, vector<int>& coloration) {

    if (coloration[u] > 0) return;
    coloration[u] = color;

    // cout << u << " " << coloration[u] <<  " " << color << endl;

    for (auto &v : g[u]) {
        if ((u != banned.first || v != banned.second) && (v != banned.first || u != banned.second)) {
            // cout << u << " " << v << endl;
            dfsfill(g, v, color, banned, coloration);
        }
    }

}

int main() {

    int n;
    cin >> n;

    vector<vector<int>> g(n);

    for (int i = 0; i< n-1; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    vector<int> acc(n, 0);
    vector<bool> side(n, false);
    vector<bool> visited(n, false);

    bool start = false;
    pair<int, int> edge;
    dfs(g, 0, -1, acc, start, edge, visited);

    if (start) {
        cout << "Yes" << endl;
        vector<int> color(n, 0);
        dfsfill(g, edge.first, 1, edge, color);
        dfsfill(g, edge.second, 2, edge, color);
        for (int i = 0; i < n; i++) {
            cout << ((color[i] == 1) ? 'U' : 'M');
        }
        cout << endl;
    } else {
        cout << "No" << endl;
    }
    


}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: ACCEPTED

Test 33

Verdict: ACCEPTED

Test 34

Verdict: ACCEPTED

Test 35

Verdict: ACCEPTED

Test 36

Verdict: ACCEPTED

Test 37

Verdict: ACCEPTED

Test 38

Verdict: ACCEPTED

Test 39

Verdict: ACCEPTED

Test 40

Verdict: ACCEPTED

Test 41

Verdict: ACCEPTED

Test 42

Verdict: ACCEPTED

Test 43

Verdict: ACCEPTED

Test 44

Verdict: ACCEPTED

Test 45

Verdict: ACCEPTED

Test 46

Verdict: ACCEPTED

Test 47

Verdict: ACCEPTED

Test 48

Verdict: ACCEPTED

Test 49

Verdict: ACCEPTED

Test 50

Verdict: ACCEPTED

Test 51

Verdict: ACCEPTED

Test 52

Verdict: ACCEPTED

Test 53

Verdict: ACCEPTED

Test 54

Verdict: ACCEPTED

Test 55

Verdict: ACCEPTED

Test 56

Verdict: ACCEPTED

Test 57

Verdict: ACCEPTED

Test 58

Verdict: ACCEPTED

Test 59

Verdict: ACCEPTED

Test 60

Verdict: ACCEPTED

Test 61

Verdict: ACCEPTED