题解 | E.小红玩树

想复杂了，直接两次BFS，分别求出a,b到所有点的距离，然后遍历所有度为1的节点（叶节点），如果存在dist_a[i]<dist_b[i]/2，说明小红能先到，否则，小红不能先到

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

// BFS工具函数：从start出发，计算所有节点的距离
vector<int> bfs(int start, int n, const vector<vector<int>>& adj) {
    vector<int> dist(n + 1, INT_MAX);  // 初始距离无穷大
    queue<int> q;
    q.push(start);
    dist[start] = 0;  // 起点距离为0

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        for (int neighbor : adj[node]) {
            if (dist[neighbor] == INT_MAX) {  // 未访问
                dist[neighbor] = dist[node] + 1;
                q.push(neighbor);
            }
        }
    }
    return dist;
}

void solve() {
    int n, a, b;
    cin >> n >> a >> b;
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 1. 计算a到所有节点的距离（小红的时间）
    vector<int> dist_a = bfs(a, n, adj);
    // 2. 计算b到所有节点的距离（小紫的距离，时间=ceil(dist_b/2)）
    vector<int> dist_b = bfs(b, n, adj);

    // 3. 遍历所有叶子节点，检查是否存在小红先到的情况
    bool red_win = false;
    for (int L = 1; L <= n; L++) {
        // 叶子节点：度数为1（树的叶子定义）
        if (adj[L].size() == 1) {
            // 小红到L的时间：dist_a[L]
            // 小紫到L的时间：ceil(dist_b[L] / 2) = (dist_b[L] + 1) / 2
            if (dist_a[L] < (dist_b[L] + 1) / 2) {
                red_win = true;
                break;  // 找到一个就够了，小红胜
            }
        }
    }

    cout << (red_win ? "red" : "purple") << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}