14275: 【原4275】憨憨的石楠树

题目描述

author: ZSTU 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4275

问题描述

铁憨憨家门前有两棵树，一棵是石楠树，另一棵也是石楠树。

不妨把这两棵树分别记为$T_a, T_b$。这两棵树都各有$n$个结点，分别从$1$到$n$编号，但是这两棵树的形态可能完全不同。

同时，铁憨憨还有一个图$G$，$G$由$m$个结点组成，编号从$1$到$m$。图$G$中没有任何边，因为铁憨憨把这些边都存在了那两棵树的结点上。换句话说，对于$T_a$上的任意一个结点$i$，都存储着一条$G$中的无向边$(u_{a,i},v_{a,i})$，对于$T_b$上的任意一个结点$i$，也存储着一条$G$中的无向边$(u_{b,i},v_{b,i})$。

现在铁憨憨想做这样一个事情：

铁憨憨首先想出了一个编号$i (1 \le i \le n)$，接着铁憨憨会把$T_a$这棵树上从$1$到$i$的最短路径上的所有结点（包括结点1和结点n）存储的边都取出来，再同样地把$T_b$上从$1$到$i$的最短路径上的所有结点上存储的边都取出来。然后铁憨憨会把他在这两棵树上得到的这些边添加到图$G$中，并计算出此时图$G$的连通块的数量，记为$f_i$。最后铁憨憨会把这些取出的边重新存回那两棵树上，图$G$恢复到没有边的状态。

而你则需要输出$f_1,f_2,\cdots,f_n$。

输入格式

第1行两个整数 $T$，表示数据组数。

对于每一组数据：

第1行两个整数 $n,m$，表示树的结点个数和图的结点个数。

接下来的 $n$ 行，每行2个整数 $(u_{a,i},v_{a,i})$，表示$T_a$上编号为$i$的结点存储的边。

再接下来 $n-1$ 行，每行2个整数$(e_{a,i,1},e_{a,i,2})$，描述$T_a$ 的一条边。

接下来的 $n$ 行，每行2个整数 $(u_{b,i},v_{b,i})$，表示$T_b$上编号为$i$的结点存储的边。

再接下来 $n-1$ 行，每行2个整数$(e_{b,i,1},e_{b,i,2})$，描述$T_b$ 的一条边。

输出格式

对于每一组测试数据，输出$n$行，第$i$行表示$f_i$。

样例输入

样例输出

样例解释

第一组数据的解释如图：

数据规模

对于所有的数据，$T\le 5, n\le 20000, m\le 20000$，$1\le u_{a,i},v_{a,i},u_{b,i},v_{b,i} \le m$，$1\le e_{a,i,1},e_{a,i,2},e_{b,i,1},e_{b,i,2} \le n$。

本题由10个测试点组成，通过每一个测试点得到10分。部分测试点的特性如下：

| 测试点 | 特性 | | ------ | ------------------------------------------------ | | 1~4 | $n,m\le 500$ | | 5~6 | 两棵树的形态完全相同，且每个节点存储的边相同 | | 7~8 | 两棵树的形态完全相同，但每个节点储存的边可能不同 | | 9~10 | 无 |

Oops! 本题目还没有解答！

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

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

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