Skip to content

11340: 【原1340】tree

题目

题目描述

author: Online Judge 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1340 

问题描述

在死神的睡梦中,同学们正坐在高中机房里学习一门叫做树的结构的课程,死神棒棒的学长正在教他写动态树。用脚趾头想想也知道,死神学不会这么难的东西,真是讨厌死了。死神好想出一道动态树的题啊!但是不用担心,因为死神连标程都写不出来。他就无聊地在课本子乱涂乱画,想象着五彩缤纷的生活将会发生多么有趣的事情。于是就歪打正着的有了接下来的这道题。

死神会给你一棵n个节点的树,就是你们最熟悉的那一种树。

死神又笃定某些边在不远的将来会有不同凡响的意义,他想知道在这棵树里有多少条路径(起点与终点不能够相同呦!并且a->b与b->a对于死神来说没有任何区别)包含所有这些特殊的边。

最后再给个小tip,千万不要往动态树的方向想,我完全没有那个意思。

输入格式

第一行唯一的整数test,表示数据组数;

接下来test块,每块第一行两个整数n,m,意即树包含的节点数以及特殊边的数目;

紧接着n-1行,每行两个整数x,y,表示树的一条边;

然后是一行m个整数,表示特殊边的编号;

输出格式

对于每组数据,一行一个整数表示答案;

Sample input

3
2 1
1 2
0
3 1
1 2
2 3
1
7 3
1 6
1 2
1 5
2 4
4 7
2 3
0 5 4

Sample output

1
2
0

数据范围

对于50%的数据,\( test \leq 10,1 \leq n \leq 100 \);

对于100%的数据,\( test \leq 100,1 \leq n \leq 20000 \);

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!