#PQJ1858x9645. QOJ 1858_9645

    ID: 2737 传统题 4000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:2024-2025 集训队互测最短路径线段树

QOJ 1858_9645

标题: 字符游戏 - Problem - QOJ.ac

#9645. 字符游戏

Statistics

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 的限制。