#P6781. [2019备战noi]barbecue
[2019备战noi]barbecue
Barbecue
题目描述
Lyra 想从一棵树上砍下一部分作为烧烤燃料。她要求砍下来的节点组成一个连通块,并且节点编号连续。
给定一棵有 个节点、节点编号为 到 的树,求有多少个不同的区间 ,使得编号为 的所有节点在树中诱导出的子图连通。
单个节点构成的区间也符合条件。
输入格式
第一行一个正整数 ,表示数据组数。
每组数据:
- 第一行一个正整数 。
- 接下来 行,每行两个整数 ,表示树上的一条无向边。
输出格式
每组数据输出一行一个整数,表示符合条件的区间数。
样例输入
2
2
2 1
4
3 4
1 4
4 2
样例输出
3
7
样例解释
第一组数据中,、、 符合条件。
第二组数据中,、、、、、、 共七个区间符合条件。
数据范围
- 对于 的数据,。
- 对于 的数据,。
- 另有 的数据,输入的树是一条链。
- 对于所有数据,,,所有数据组的 之和不超过 。