#PQJ1858x9645. QOJ 1858_9645
QOJ 1858_9645
标题: 字符游戏 - Problem - QOJ.ac
#9645. 字符游戏
The problem was used in the following contests:
题目描述
Alice 和 Bob 正在玩游戏。初始时有一个字符串可重集 S,Alice 和 Bob 轮流操作,Alice 先手。每次可以选择一个 S 中的字符串 s,将其从 S 中删除,并选择一个在 s 中出现过的字符 c,将 s 中的所有字符 c 删除,并沿着这些删除的位置将 s 划分成若干子串,将这些子串中非空的加入进集合 S。不能进行操作的人输。
现在给定一棵树,节点数为 n,每个节点上有字符。记 path(u,v) 表示将节点 u 到 v 的最短路径所经过的节点(包括 u 和 v)上的字符依次拼接而成的字符串。共 q 次询问,每次询问给定 u 和 v,求 S={path(u,v)} 时的胜者。若 Alice 获胜,同时输出第一步有多少种走法。
输入格式
从标准输入读入数据。
第一行输入两个正整数 n 和 q。
第二行输入一个长度为 n 的字符串 s,其第 i 位 si 表示节点 i 上的字符。
接下来的 n−1 行,每行两个正整数 u 和 v,描述树上的一条边。
接下来的 q 行,每行两个正整数 u 和 v,代表一组询问。
输出格式
输出到标准输出。
输出共 q 行。对于每组询问,若 Alice 获胜,输出 Alice 以及第一步的走法数,以空格分开。否则,输出 Bob。
样例
样例 1 输入
10 10
1412002124
1 2
2 3
3 4
4 5
4 6
5 7
5 8
6 9
7 10
7 6
10 2
8 8
7 2
2 9
1 7
5 1
3 8
1 2
7 1
样例 1 输出
Alice 2
Alice 1
Alice 1
Alice 1
Alice 1
Bob
Alice 1
Alice 1
Bob
Bob
子任务
保证对于所有测试点满足:1≤n≤5×104,1≤q≤105,0≤si<10。
子任务编号 n≤ q≤ si≤ 特殊性质 分数 1 10 103 10 无 7 2 500 2×104 10 A 13 3 3,000 2×104 10 A 12 4 5×104 105 10 A 19 5 2×104 2×104 5 无 24 6 5×104 105 10 无 25
特殊性质 A:保证树的形态为一条链。
下发文件中的 $i.in/$i.ans 满足子任务 i 的限制。