C++(g++ 7.5.0) 解法, 执行用时: 145ms, 内存消耗: 7156K, 提交时间: 2023-05-07 23:47:04

#include <bits/stdc++.h>

using namespace std;

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

const int mod=1e9+7,N=1e5+10;

int n,m,k;
int sg[N];
vector<int> e[N];

void dfs(int u,int fa)
{
    int res=0;
    for(auto v : e[u])
    {
        if(v==fa) continue;
        dfs(v,u);
        res^=(sg[v]+1);
    }
    sg[u]=res;
}
    

void solve()
{
    cin >> n;
    for(int i=1;i<=n;i++) e[i].clear();
    for(int i=1;i<n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        e[a].push_back(b);
        e[b].push_back(a);
    }
    dfs(1,0);
    if(sg[1]) puts("Alice");
    else puts("Bob");
}

int main()
{
    int _;
    cin >> _;
    while(_--) solve();
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 284ms, 内存消耗: 7136K, 提交时间: 2022-08-14 17:03:15

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
vector<int> g[N];
int f[N];
int dfs(int x,int fa)
{
	if(f[x]!=-1) return f[x];
	f[x]=0;
	for(auto d:g[x])
	{
		if(d==fa) continue;
		f[x]^=(dfs(d,x)+1);
	}
	return f[x];
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		for(int i=1;i<=n;i++) g[i].clear();
		memset(f,-1,sizeof(f));
		for(int i=1;i<=n-1;i++)
		{
			int x,y;
			cin>>x>>y;
			g[x].push_back(y);
			g[y].push_back(x);
		}
		int fin=dfs(1,-1);
		if(fin) cout<<"Alice\n";
		else cout<<"Bob\n";
	}
}