Cerinta completa

Alice and Bob are playing a game with a rooted tree. The tree has vertices and the first node, , is always the root. Here are the basic rules:

  1. They move in alternating turns, and both players always move optimally.
  2. During each move, a player removes an edge from the tree, disconnecting one of its leaves or branches. The leaf or branch that was disconnected from the rooted tree is removed from the game.
  3. The first player to be unable to make a move loses the game.
  4. Alice always makes the first move.

For example, the diagram below shows a tree of size , where the root is node :
tree-initial.png

Now, if a player removes the edge between and , then nodes and become disconnected from the root and are removed from the game:

tree-removed.png

Given the structure of the tree, determine and print the winner of the game. If Alice wins, print ; otherwise print .

Input Format

The first line contains a single integer, , denoting the number of test cases.
For each test case, the first line contains an integer, , denoting the number of nodes in the tree.
Each of the subsequent lines contains space-separated integers, and , defining an edge connecting nodes and .

Constraints

Output Format

For each test case, print the name of the winner (i.e., or ) on a new line.

Sample Input

1
5
1 2
3 1
3 4
4 5

Sample Output

Alice

Explanation

Test Case 0:

Alice removes the edge connecting node to node , effectively trimming nodes and from the tree. Now the only remaining edges are and . Because Bob can’t remove both of them, Alice will make the last possible move. Because the last player to move wins, we print on a new line.

Limbajul de programare folosit: java8

Cod:

import java.io.*;
import java.util.*;

public class Solution {
    private static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { this.in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        int nextInt() throws IOException {
            int c;
            do { c = read(); } while (c <= ' ' && c != -1);
            int sign = 1;
            if (c == '-') { sign = -1; c = read(); }
            int val = 0;
            while (c > ' ') {
                val = val * 10 + (c - '0');
                c = read();
            }
            return val * sign;
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int t = fs.nextInt();
        StringBuilder out = new StringBuilder();

        while (t-- > 0) {
            int n = fs.nextInt();
            @SuppressWarnings("unchecked")
            ArrayList<Integer>[] g = new ArrayList[n + 1];
            for (int i = 1; i <= n; i++) g[i] = new ArrayList<>();

            for (int i = 0; i < n - 1; i++) {
                int u = fs.nextInt();
                int v = fs.nextInt();
                g[u].add(v);
                g[v].add(u);
            }

            int[] parent = new int[n + 1];
            int[] order = new int[n];
            int ord = 0;
            int[] stack = new int[n];
            int top = 0;
            stack[top++] = 1;
            parent[1] = -1;

            while (top > 0) {
                int u = stack[--top];
                order[ord++] = u;
                for (int v : g[u]) {
                    if (v == parent[u]) continue;
                    parent[v] = u;
                    stack[top++] = v;
                }
            }

            int[] sg = new int[n + 1];
            for (int i = n - 1; i >= 0; i--) {
                int u = order[i];
                int val = 0;
                for (int v : g[u]) {
                    if (v == parent[u]) continue;
                    val ^= (sg[v] + 1);
                }
                sg[u] = val;
            }

            out.append(sg[1] != 0 ? "Alice" : "Bob").append('\n');
        }

        System.out.print(out);
    }
}

Scor obtinut: 1.0

Submission ID: 464617924

Link challenge: https://www.hackerrank.com/challenges/deforestation-1/problem

Deforestation