主页 讨论版 问题 名次 状态 统计
欢迎加入西电微软俱乐部招新群 588166170,做出福利题,免技术部第一次面试且赠送“福利”海报或小礼品~~~~
问题 B: 路径计数

问题 B: 路径计数

时间限制: 1 Sec  内存限制: 128 MB
提交: 125  解决: 73
[提交][状态][讨论版]

题目描述

一个无向无环的图被称为树。任意两点u到v的路径有且仅有一条。xry111对这个树产生了兴趣,他觉得有一些边比别的更重要。于是它定义边的重要度为所有路径中经过这条边的路径数。但是他太弱了,解决不了这么难的问题。请你帮他计算重要度。

输入

多组数据。第一行一个整数t,表示数据组数。每组第一行两个整数n,m。n为点数,m为询问数。接下来n-1行,每行两个整数u,v表示u到v有一条边。接下来m行,每行一个整数q,表示询问第q条边的重要度。
范围
t<=5
2<=n<=1000
1<=m<=n-1

输出

每组m行,即m个询问的答案。

样例输入

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

样例输出

6
4
4

提示

对于第4条边,有1到5,2到5,3到5,4到5。共四条路径经过它。


[提交][状态][讨论版]