Skip to content

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$。

样例输入

2
3 4
1 2
2 3
3 4
1 2
1 3
1 3
2 4
3 4
1 2
2 3
2 100
100 99
99 98
1 2
97 96
95 94
1 2

样例输出

2
1
1
98
96

样例解释

第一组数据的解释如图:

sample

数据规模

对于所有的数据,$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了,可以的话,请您参考添加页面,与大家一起分享你的题解!