#OJ2287. Colorful Tree
Colorful Tree
Colorful Tree
Time Limit: 1 Sec Memory Limit: 128 MB
Description
给你一棵树,树上的每个结点都有一个重量,每条边都有一个长度。求出每个结点到根节点的距离以及所在子树上所有结点的重量之和。(根节点为1)
Input
第一行为一个正整数T,代表样例组数。 每组样例的第一行为一个正整数n(1<=n<=10000),代表结点个数。 接下来一行有n个正整数ai(i∈[1,n],1<=ai<=100),代表每个节点的重量。 接下来有n-1行,每行有三个正整数u,v,x(1<=u,v<=n,1<=x<=100),表示结点u与结点v之间有一条长度为x的边,且u为v的父节点。 保证所有的n加起来不超过100000。
Output
对于每组样例,第一行输出"Case #x:",x为样例序号。 第二行输出每个节点到根节点的距离。 第二行输出每个节点所在子树上所有结点的重量之和。(从1到n依次输出)
Sample Input
1
5
1 2 3 4 5
1 2 4
1 3 3
2 4 2
2 5 1
Sample Output
Case #1:
0 4 3 6 5
15 11 3 4 5
HINT
关于树的概念及建立方法可自行查阅相关资料 注意体会递推和回归在搜索过程中的作用