P4427 [BJOI2018]求和

    • 189通过
    • 656提交
  • 题目提供者 oscar
  • 评测方式 云端评测
  • 标签 倍增 前缀和 最近公共祖先,LCA 树链剖分,树剖 各省省选 2018 北京 O2优化
  • 难度 提高+/省选-
  • 时空限制 2000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    master 对树上的求和非常感兴趣。他生成了一棵有根树,并且希望多次询问这棵树上一段路径上所有节点深度的 $k$ 次方和,而且每次的 $k$ 可能是不同的。此处节点深度的定义是这个节点到根的路径上的边数。他把这个问题交给了pupil,但pupil 并不会这么复杂的操作,你能帮他解决吗?

    输入输出格式

    输入格式:

    第一行包含一个正整数 $n$ ,表示树的节点数。

    之后 $n-1$ 行每行两个空格隔开的正整数 $i, j$ ,表示树上的一条连接点 $i$ 和点 $j$ 的边。

    之后一行一个正整数 $m$ ,表示询问的数量。

    之后每行三个空格隔开的正整数 $i, j, k$ ,表示询问从点 $i$ 到点 $j$ 的路径上所有节点深度的 $k$ 次方和。由于这个结果可能非常大,输出其对 $998244353$ 取模的结果。

    树的节点从 $1$ 开始标号,其中 $1$ 号节点为树的根。

    输出格式:

    对于每组数据输出一行一个正整数表示取模后的结果。

    输入输出样例

    输入样例#1: 复制
    5
    1 2
    1 3
    2 4
    2 5
    2
    1 4 5
    5 4 45
    输出样例#1: 复制
    33
    503245989

    说明

    样例解释

    以下用 $d (i)$ 表示第 $i$ 个节点的深度。

    对于样例中的树,有 $d (1) = 0, d (2) = 1, d (3) = 1, d (4) = 2, d (5) = 2$ 。

    因此第一个询问答案为 $(2^5 + 1^5 + 0^5)\ mod\ 998244353 = 33$ ,第二个询问答案为 $(2^{45} + 1^{45} + 2^{45})\ mod\ 998244353 = 503245989$ 。

    数据范围

    对于 $30\%$ 的数据, $1 \leq n,m \leq 100$ 。

    对于 $60\%$ 的数据, $1 \leq n,m \leq 1000$ 。

    对于 $100\%$ 的数据, $1 \leq n,m \leq 300000, 1 \leq k \leq 50$ 。

    另外存在5个不计分的hack数据

    提示

    数据规模较大,请注意使用较快速的输入输出方式。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。