Submission #1412020

---

Source Code Expand

#include <iostream>
#include <sstream>
#include <fstream>

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <numeric>
#include <functional>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <utility>
#include <bitset>
#include <limits>
#include <climits>
using namespace std;

#ifdef DEBUG
#define NDEBUG
#endif
#undef NDEBUG
#include <cassert>

typedef long long ll;
typedef pair<int, int> ii;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))



int solve(vector<vector<int>>& ne) {
    vector<int> xors;

    int N = ne.size();
    vector<int> parent(N);
    vector<vector<int>> children(N);
    parent[0] = -1;
    queue<int> q;
    q.push(0);
    vector<int> r;
    vector<int> visited(N, false);
    while (!q.empty()){
        int u = q.front(); q.pop();
        r.push_back(u);
        visited[u] = true;
        for (int v : ne[u]) {
            if (visited[v]) continue;
            parent[v] = u;
            children[u].push_back(v);
            q.push(v);
        }
    }
    reverse(ALL(r));
    vector<vector<int>> legs(N);
    // cout << parent << endl;
    // cout << r << endl;
    rep(i,N) {
        int v = r[i], u = parent[v];

        int L = legs[v].size();
        int msg = -1;
        switch (L) {
            case 0:
                msg = 1;
                if (v == 0) xors.push_back(msg);
                break;
            case 1:
                msg = legs[v][0] + 1;
                if (v == 0) xors.push_back(msg);
                break;
            default:
                int x = 0;
                rep(i, L) x ^= legs[v][i];
                xors.push_back(x);
                msg = 1;
                break;
        }
        if (u != -1 && msg != -1) {
            legs[u].push_back(msg);
        }
    }

    int ans = 0;
    for (int x : xors) ans += x;

    return ans;
}

int main(){
    int N; cin >> N;
    vector<vector<int>> ne(N);
    rep(i, N-1) {
        int x, y; cin >> x >> y;
        --x; --y;
        ne[x].pb(y); ne[y].pb(x);
    }
    int ans = solve(ne);
    cout << (ans == 0 ? "Bob" : "Alice") << endl;
    return 0;
}

Submission Info

Judge Result