提示: 欢迎访问OurACM平台。
Problem 2176 easy problem

Accept: 58    Submit: 214
Time Limit: 2000 mSec    Memory Limit : 32768 KB

Problem Description

给定一棵n个节点以1为根的树,初始每个节点的值为0,现在我们要在树上进行一些操作,操作有两种类型。

1 x val 表示对以x为根的子树的每个点进行加权操作(我们定义每个节点的深度为每个节点到根1的距离),如果 y是以x为根的子树中的点那么 y节点的权值增加 ((dep[y]-dep[x])%k+1)*val 其中dep[y]表示y节点的深度,k为一个常数(1<=k<=5)

2 x 查询当前x节点的权值。

Input

首先输入一个整数T 表示数据的组数,每组数据 第一行有3个整数 n ,m, k(1<=n,m<=50000, 1<=k<=5) 。n表示节点数,m表示操作数,k表示如题目描述的常数。

接下去n-1行描述一棵树。接下去m行每行表示 一个操作 有两种类型1 x val 表示第一种类型 2 x 表示第二种类型。(1<=x<=n,1<=val<=100)

Output

每组数据首先输出 Case#x: 表示第x组数据 x从1开始。接下去对于每组数据中的每个查询操作输出查询结果。(具体输出格式看样例)

Sample Input

1 5 7 2 1 2 2 4 2 5 1 3 1 2 3 1 1 2 2 1 2 2 2 3 2 4 2 5

Sample Output

Case#1: 2 7 4 8 8

Source

FOJ有奖月赛-2014年11月

Submit  Back  Status  Discuss