Portal --> broken qwq
Description
初始的时候给你一棵树，每个节点上有一个正整数，这棵树经过一些操作之后可能变成一个森林，两个人轮流选择当前森林中的一棵树的树根，将该节点上面的数(K)变成([K/a])（下取整，(ain [2,K+1])），当一个节点上的数变成(0)之后，这个节点会消失然后其所有儿子都会变成新的树根，如果一个人操作后森林中没有节点了那么该玩家获胜，求先手（(Alice)）还是后手（(Marisa)）有必胜策略
数据范围：(n<=100000)，节点上的数不超过(2^{63})
Solution
首先你的语文要好才能做出这题qwq注意数据范围是不超过，所以我们要用unsigned long long。。
然后考虑转化一下问题（所以为什么我想到怎么转化但是不会做==）
我们可以把问题转成一个取石子的模型，因为每个点至多操作(log_2val+1)次，然后。。因为(ain [2,val+1])所以。。总能让这个新的(val)（记为(val')）满足(log_2val'+1)等于一个小于(log_2val+1)的数，并且任意一个这个范围内的数都可以取到，所以。。。我们就看成一个节点上有(log_2val)个石子，每次都要取一个根节点上的至少一颗石子这样就好了
然后。。接下来的事情就是。。(sg)函数
根据(sg)定理，一个局面的(sg)值为其拆成的子游戏的(sg)值的异或和，考虑当(val=0)的情况，这个节点的(sg)值应该就是其儿子的(sg)值异或和（因为。。(val=0)就相当其每一个儿子都是它拆出来的一个子游戏，而一个人在其中一个儿子的树中操作并不会影响到别的儿子的树，所以它们是相互独立的（一开始我的理解是错的，并不是说不能中途对其他子游戏操作，而是两个子游戏互不影响即算为独立））
然后我们就可以得到(val=0)时的(sg)值，接下来要用的就是(sg)的另一个求法：一个局面的(sg)值是其后继局面的(sg)值的(mex)，所以我们先取一次(mex)得到(val=1)的时候的(sg)值，再(mex)一次得到(val=2)的，以此类推。。然后我们就可以得到这个节点实际上的(sg)值啦
最后我们根据(sg[1])判断先手获胜还是后手获胜即可
代码大概长这个样子
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define ull unsigned long long
using namespace std;
const int N=1e5+10;
struct xxx{
int y,nxt;
}a[N*2];
int h[N],val[N],in[N],sg[N];
int vis[N];
int n,m,tot,T,mark;
void add(int x,int y){a[++tot].y=y; a[tot].nxt=h[x]; h[x]=tot;}
void init(){
memset(h,-1,sizeof(h));
tot=0;
memset(sg,0,sizeof(sg));
}
void dfs(int fa,int x){
int u,son=0,ret=0,cnt;
for (int i=h[x];i!=-1;i=a[i].nxt){
u=a[i].y;
if (u==fa) continue;
++son;
dfs(x,u);
ret^=sg[u];
}
++mark;
vis[ret]=mark;
cnt=0;
sg[x]=0;
for (int i=1;i<=val[x];++i){
while (vis[sg[x]]==mark) ++sg[x];
vis[sg[x]]=mark;
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
#endif
ull tmp;
int x,y;
while (scanf("%d",&n)!=EOF){
for (int i=1;i<=n;++i){
cin>>tmp;
val[i]=(int)(log(1.0*tmp)/log(2.0))+1;
}
init();
for (int i=1;i<n;++i){
scanf("%d%d",&x,&y);
++x; ++y;
add(x,y); add(y,x);
}
dfs(0,1);
if (sg[1]) printf("Alice
");
else printf("Marisa
");
}
}