二叉树游戏

NC236262. 二叉树游戏

描述

Alice和Bob在玩二叉树游戏，游戏规则如下：给一个 $n$ 个节点的二叉树，根节点是1，两人轮流操作。每次操作可以取走一棵完全二叉子树，当一名玩家不能操作时则视为失败，Alice先手。如果两个人都以最优策略来进行游戏，请问最终谁能获胜

对于一棵二叉树，如果它的所有非叶子节点都有两个子结点，并且所有叶子节点的深度相同，那么这棵二叉树是完全二叉树。显然，如果一棵树只有一个节点，那么它也是完全二叉树。

输入描述

第一行输入一个整数 $n(1\le n \le 5\times 10^5)$ ，表示二叉树的结点个数。

接下来 $n-1$ 行，每一行输入两个整数 $u_i,v_i(1\le u_i,v_i \le n)$ ，表示节点 $u_i,v_i$ 之间有一条连边。保证输入是一棵二叉树。

输出描述

输出一行，如果Alice必胜，则输出"Alice"；如果Bob必胜，则输出"Bob"。

示例1

输入:

3
1 2
2 3

输出:

Alice

示例2

输入:

输出:

Bob

上次编辑到这里，代码来自缓存点击恢复默认模板

Java 解法, 执行用时: 45ms, 内存消耗: 10848K, 提交时间: 2023-07-15 12:45:59

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        if(n%2==1)System.out.println("Alice");
        else System.out.println("Bob");
        
        
    }
}

C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 432K, 提交时间: 2022-08-25 14:45:44

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4+666;
int main()
{
	int n , i , u , v;
	cin >> n ;
	
	if(n % 2 == 1)  cout << "Alice";
	else cout << "Bob" ;
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 2ms, 内存消耗: 408K, 提交时间: 2023-08-08 16:13:03

#include<stdio.h>
int main()
{
    int n;scanf("%d",&n);
    if(n&1)printf("Alice");
    else printf("Bob");
}