树上游戏

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

int main()
{
    int n = 0;
    cin >> n;
    while (cin >> n)
    {
        unordered_map<int, vector<int>> ump;
        for (int i = 0; i < n-1; i++)
        {
            int x, y;
            cin >> x >> y;
            ump[x].push_back(y);
            ump[y].push_back(x);
        }
        vector<pair<int, vector<int>>> tree(n+1, make_pair(-1, vector<int>()));
        tree[1].first = 0;
        queue<int> q;
        q.push(1);
        while (!q.empty())
        {
            int cur = q.front();
            q.pop();
            for (int i : ump[cur])
            {
                if (tree[i].first == -1)
                {
                    tree[i].first = cur;
                    tree[cur].second.push_back(i);
                    q.push(i);
                }
            }
        }
        vector<int> path;
        int root = n;
        while (root != 0)
        {
            path.push_back(root);
            root = tree[root].first;
        }

        int whiteroot = path[-1 + path.size() / 2];
        q = queue<int>();
        q.push(whiteroot);
        int whitesize = 0;
        while (!q.empty())
        {
            int cur = q.front();
            q.pop();
            whitesize++;
            for (int child : tree[cur].second)
            {
                q.push(child);
            }
        }
        int blacksize = n - whitesize;
        if (blacksize > whitesize)
        {
            cout << "niuniu" << endl;
        }
        else
        {
            cout << "niumei" << endl;
        }
    }
    return 0;
}

#include <iostream>
#include <array>
#include <vector>
using namespace std;

const int MAXN = 1e5;

array<vector<int>, MAXN> edges;
array<int, MAXN> next_index;
vector<int> path;

int dfs(int start, int dest){
    path.clear();
    next_index.fill(-1);
    path.emplace_back(start);
    next_index[start] = 0;
    int count = 1;
    while(!path.empty() && path.back() != dest){
        int p = path.back();
        while(next_index[p] < edges[p].size() && next_index[edges[p][next_index[p]]] > 0) next_index[p]++;
        if(next_index[p] >= edges[p].size()) path.pop_back();
        else{
            int expand = edges[p][next_index[p]];
            path.emplace_back(expand);
            next_index[expand] = 0;
            count++;
            next_index[p]++;
        }
    }
    return count;
}

int main(){
    int T;
    cin >> T;
    for(int t = 0; t < T; t++){
        int n, a, b;
        cin >> n;
        for(int i = 0; i < n; i++) edges[i].clear();
        for(int i = 0; i < n - 1; i++){
            cin >> a >> b;
            edges[a - 1].emplace_back(b - 1);
            edges[b - 1].emplace_back(a - 1);
        }
        
        // 从0深搜找n-1顶点, 找到时停止
        dfs(0, n - 1);

        // 找到path中间黑和白的关键节点, 让黑关键节点断掉与白节点联系, 进行深搜统计节点数
        int black_key = path[(path.size() - 1) / 2];
        int white_key = path[(path.size() + 1) / 2];
        for(auto it = edges[black_key].begin(); it != edges[black_key].end(); it++){
            if(*it == white_key){
                edges[black_key].erase(it);
                break;
            }
        }
        int black_count = dfs(black_key, -1);
        int white_count = n - black_count;
        if(black_count > white_count) cout << "niuniu\n";
        else cout << "niumei\n";
    }
}