#P6781. [2019备战noi]barbecue

    ID: 6601 传统题 2500ms 1024MiB 尝试: 2 已通过: 1 难度: 7 上传者: 标签>难度分类提高+/省选-计算几何扫描线数据结构懒标记线段树模拟与实现技巧增量维护CF2200

[2019备战noi]barbecue

Barbecue

题目描述

Lyra 想从一棵树上砍下一部分作为烧烤燃料。她要求砍下来的节点组成一个连通块,并且节点编号连续。

给定一棵有 nn 个节点、节点编号为 11 到 nn 的树,求有多少个不同的区间 [L,R][L,R],使得编号为 L,L+1,…,RL,L+1,\ldots,R 的所有节点在树中诱导出的子图连通。

单个节点构成的区间也符合条件。

输入格式

第一行一个正整数 TT,表示数据组数。

每组数据:

  • 第一行一个正整数 nn。
  • 接下来 n−1n-1 行,每行两个整数 u,vu,v,表示树上的一条无向边。

输出格式

每组数据输出一行一个整数,表示符合条件的区间数。

样例输入

2
2
2 1
4
3 4
1 4
4 2

样例输出

3
7

样例解释

第一组数据中,[1,1][1,1]、[1,2][1,2]、[2,2][2,2] 符合条件。

第二组数据中,[1,1][1,1]、[1,4][1,4]、[2,2][2,2]、[2,4][2,4]、[3,3][3,3]、[3,4][3,4]、[4,4][4,4] 共七个区间符合条件。

数据范围

  • 对于 20%20\% 的数据,n≤300n\le300。
  • 对于 40%40\% 的数据,n≤2000n\le2000。
  • 另有 20%20\% 的数据,输入的树是一条链。
  • 对于所有数据,T≤15T\le15,1≤u,v≤n≤3×1051\le u,v\le n\le3\times10^5,所有数据组的 nn 之和不超过 2×1062\times10^6。