#PQJ467x2578. QOJ 467_2578
QOJ 467_2578
3 Minimax 搜索 3.1 题目描述 九条可怜是一个喜欢玩游戏的女孩子。为了增强自己的游戏水平,她想要用理论的武器武 装自己。这道题和著名的Minimax 搜索有关。 可怜有一棵有根树,根节点编号为1。定义根节点的深度为1,其他节点的深度为它的父亲 的深度加一。同时在叶子节点权值给定的情况下,可怜用如下方式定义了每一个非节点的权值: • 对于深度为奇数的非叶子节点,它的权值是它所有子节点的权值最大值。 • 对于深度为偶数的非叶子节点,它的权值是它所有子节点的权值最小值。 最开始,可怜令编号为i 的叶子节点权值为i,并计算得到了根节点的权值为W。 现在,邪恶的Cedyks 想要通过修改某些叶子节点的权值,来让根节点的权值发生改变。 Cedyks 设计了一个量子攻击器,在攻击器发动后,Cedyks 会随机获得一个非空的叶子节点集 合S 的控制权,并可以花费一定的能量来修改S 中的叶子节点的权值。 然而,修改叶子节点的权值也要消耗能量,对于S 中的叶子节点i,它的初始权值为i,假 设Cedyks 把它的权值修改成了wi(wi 可以是ӏ意整数,ࣙ ᣀ䋳数),则Cedyks 在这次攻击 中,需要花费的能量为maxi∈S |i −wi|。 Cedyks 想要尽可能节约能量,于是他总是会以最少的能量来ᅠ成攻击,即在花费的能量最 小的情况下,让根节点的权值发生改变。令w(S) 为Cedyks 在获得了集合S 的控制权后,会 花费的能量。特殊地,对于某些集合S,可能无论如何改变S 中叶子节点的权值,根节点的权 值都不会发生改变,这时,w(S) 的值被定义为n。为了方便,我们称w(S) 为S 的稳定度。 当有m 个叶子节点的时候,一共有2m −1 种不同的叶子节点的非空集合。在发动攻击前, Cedyks 想要先预估一下自己需要花费的能量。于是他给出了一个区间[L, R],他想要知道对于 每一个k ∈[L, R],有多少个集合S 满足w(S) = k。 3.2 输入Ḑ式 第一行输入三个整数n, L, R(n ≥2, 1 ≤L ≤R ≤n)。 接下来n −1 行每行两个整数u, v,表示树上的一条边。 3.3 输出Ḑ式 输出一行R −L + 1 个整数,第i 个整数表示w(S) 为L + i −1 的集合S 有多少个。答案 可能会很大,请对998244353 取模后输出。 3.4 ḋ例输入 5 1 5 8
1 5 1 4 5 3 5 2 3.5 ḋ例输出 4 0 1 0 2 3.6 ḋ例㾷䞞 最开始,在可怜的设定下(i 号叶子节点的权值为i),根节点的权值为4。 树上一共有3 个叶子节点{2, 3, 4},一共有7 个非空的叶子节点权值,其中: • {4}, {2,4}, {3,4}, {2,3,4} 的稳定度为1,只要稍微修改4 号叶子节点的权值,根节点的权 值就会发生改变。 • {2},{3} 的稳定度为5,因为5 号的权值是2, 3 的较小值,在只修改2 号或者3 号的情况 下,5 号点的权值始终小于等于3,所以根节点的权值始终为4。 • {2,3} 的稳定度为3,要让根节点的权值发生改变,必须让5 的权值大于4,因此w2, w3 都必须要大于4,所以稳定度为3,一个可行的方案是把w2, w3 都设为5。 3.7 数据㣗ೈ与约定 测试点 n 其他约定 测试点 n 其他约定 1 ≤10 L = R = n 6 ≤2 × 105 R −L ≤50 2 ≤50 7 3 8 无 4 ≤5000 9 5 10 对于100% 的数据,保证n ≥2, 1 ≤L ≤R ≤n。 9