4452. [Cerc2015]Export Estimate
#4452. [Cerc2015]Export Estimate
题目描述
给你一个n个点m条边的无向图，每条边有权值，我们可以选择一个整数lim来生成一个新的图，过程如下：
1.先将原图中边权小于lim的边删掉
2.依次从1到n枚举每个点
（a）如果这个点没有边于它相连，这个点将会被删去
（b）如果这个点只与两条不相同的边x，y相连，设这两条边的另一个点分别为a，b，如果a，b和这个点都不相同（a，b可以相同），则依次做如下操作：
（i）删去边x，y
（ii）删去这个点
（iii）在a，b之间建立一条新的边
下面这个例子lim=95：
.png)
数据保证原图没有重边和自环，但不保证经过如上操作后的图没有重边和自环。
现在我们想知道当lim取若干值时，由原图生成的新图的点数和边数是多少。
输入格式
第一行两个数n，m，表示原图有n点m条边。
接下来m行，每行三个数a，b，c，表示a和b之间有一条边权为c的双向边。
接下来一行一个数q，表示有q次询问。
接下来一行q个数，k1，k2，...，kq。
1<=n<=300000
1<=m<=300000
0<=c<=300000
1<=q<=300000
0<=ki<=300000
输出格式
总共q行，每行两个数，表示lim取ki时，生成的新图的点数和边数
样例
样例输入
Sample Input1:
6 7
1 2 20
2 3 80
2 5 100
3 5 50
3 4 100
5 6 90
4 6 100
4
25 75 85 95
Sample Input2:
10 14
2 7 150
1 2 100
2 3 150
3 1 200
1 4 60
4 5 20
2 5 100
5 6 90
6 7 120
7 5 130
6 8 50
8 9 200
9 10 200
10 7 200
5
300 50 95 100 110
样例输出
Sample Output1:
2 3
1 1
2 1
4 2
Sample Output2:
0 0
6 9
4 5
4 5
5 4