TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P4689
  • 题目
  • P4689【BJOI2018】求和
    限制 : 时间限制 : 20000 MS   空间限制 : 565536 KB
    评测说明 : 2s,512m
    问题描述

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

    输入格式

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

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

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

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

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

    输出格式

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

    样例输入

    5
    1 2
    1 3
    2 4
    2 5
    2
    1 4 5
    5 4 45

    样例输出

    33
    503245989

    提示

    对于30%的数据,1≤n,m≤100;

    对于60%的数据,1≤n,m≤1000;

    对于100%的数据,1≤n,m≤300000,1≤k≤50。

     

    样例解释
    以下用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。