怎样用自己的服务器做网站,农业展示网站模板下载,哪些网站做平面设计素材,当年的51网站Alice \text{Alice} Alice 和 Bob \text{Bob} Bob 又开始玩游戏了#xff0c;他们已经把石子堆得比山还高了#xff0c;现在他们要玩一种更新奇的游戏#xff0c;这种游戏的规则如下#xff1a;
给定一颗 n n n 个节点的树#xff0c; Alice \text{Alice} Alice 和 Bo… Alice \text{Alice} Alice 和 Bob \text{Bob} Bob 又开始玩游戏了他们已经把石子堆得比山还高了现在他们要玩一种更新奇的游戏这种游戏的规则如下
给定一颗 n n n 个节点的树 Alice \text{Alice} Alice 和 Bob \text{Bob} Bob 随机选择一个节点作为起点放上棋子由 Alice \text{Alice} Alice 先手。轮到一方后可以将这颗棋子移动到树上任意一点每次一方移动的距离必须比对方上一次移动的距离还要大开始时默认为 0 0 0。当一方不能再次移动之后判负。
现在 Alice \text{Alice} Alice 和 Bob \text{Bob} Bob 已经找到了一棵节点编号为 1 ∼ n 1∼n 1∼n 的树准备开始游戏作为博弈高手 Alice \text{Alice} Alice 和 Bob \text{Bob} Bob 均会做出最优的选择选择一个节点后他们知道游戏必然有一种必胜策略现在他们想知道游戏的胜负他们会询问你 q q q 次每次他们会选择一个节点询问你只需要回答在最优策略下以这个为节点为起点的胜者是谁即可。 由于每次移动的距离递增考虑距离最大的时候就是树的直径。这里的直径定义为一条包含最多点的路径。
显然若一个点直径的一端先手放这里一定会赢。于是“删除”原树上所有直径端点。
考虑现在的树的直径现在树的直径的端点先手也是必胜的如果先手放这里先手可以把棋子移到现在直径的另一个端点后手就只能移到原树直径的端点先手移到另一个原树直径的端点后手就操作不了了。
这样子每次删去直径的端点直径的长度减少 2 2 2仔细想想。那么如果最后减少到 1 1 1 时放这个点先手必败如果最后减少到 2 2 2显然先手必胜。
结论如果树的直径长度是奇数那么直径中间那个点 Bob \text{Bob} Bob 必胜否则 Alice \text{Alice} Alice 必胜如果是偶数所有的点都是 Alice \text{Alice} Alice 必胜。
题外话赛时我打了 70pts 暴力剩下的就总司令全输出 Alice \text{Alice} Alice拿下 95pts。不可以总司令
#includebits/stdc.h
using namespace std;
const int N1e51;
int n,q,maxdep,D;
int head[N],nxt[N1],to[N1],cnt,dep[N],fa[N];
void add(int u,int v)
{to[cnt]v;nxt[cnt]head[u];head[u]cnt;
}
void dfs(int u,int f)
{dep[u]dep[f]1;fa[u]f;if(maxdepdep[u]){maxdepdep[u];Du;}for(int ihead[u];i;inxt[i]) if(to[i]!f) dfs(to[i],u);
}
int main()
{freopen(tree.in,r,stdin);freopen(tree.out,w,stdout);scanf(%d%d,n,q);for(int i1,x,y;in;i){scanf(%d%d,x,y);add(x,y),add(y,x);}dfs(1,0);maxdep0;dfs(D,0);if(maxdep1){for(int i1;i*2maxdep;i) Dfa[D];while(q--){int x;scanf(%d,x);puts(x^D?Alice:Bob);}}else while(q--) puts(Alice);
}
