好久没有写单独一题的题解了……最近一直在写专题，2-SAT已经写了半个月了，昨天写到一道带权并查集，没怎么分析数据就直接开写了……结果一直TTTT……
题意：
一个把消费旅游看成成长标志的大学生想要出去玩。有n个城市，m条路，每条路都有耗费时间，浮躁的大学生在一条路上最多等 limit 分钟，否则他就不去。因为等待时间是固定的，他只能顺应环境，尝试改变自己的 limit ，问有q个limit，他最多能走多少不同的路线。 (起点终点有不相同即为不同）
思路：
并查集处理，得集合中的元素 n ，对每个单独的集合取 (A_n^2) 也就是 n*(n-1) ，但是 (n \le 20000,q \le 5000),如果每次都重置并跑一便并查集不用想也是要 T 的。这里有两个优化地方：
- 对每个limit排序
- 对边权排序
对每一个排序后的limit，遍历边权，如果小于当前limit就加入并查集操作，否则退出。
而对下一个limit询问就从上次退出的位置减一继续操作即可。
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#define INF 0x3f3f3f
using namespace std;
const int maxn = 2e4 + 10;
int n, m, q;
int root[maxn];
long long num[maxn];
int head[maxn];
long long ans[maxn];
struct limit_node {
long long limit;
int pos;
bool operator<(const limit_node& a) const
{
return limit < a.limit;
}
} nodes[maxn * 10];
struct node {
int from;
int to;
int val;
bool operator<(const node& a) const
{
return val < a.val;
}
} edges[maxn * 10];
int findRoot(int x)
{
return root[x] == x ? root[x] : root[x] = findRoot(root[x]);
}
void init()
{
for (int i = 0; i <= n; i++) {
num[i] = 1;
root[i] = i;
}
}
int main()
{
int T;
scanf("%d", &T);
while (T--) {
scanf("%d %d %d", &n, &m, &q);
init();
for (int i = 1; i <= m; i++)
scanf("%d %d %d", &edges[i].from, &edges[i].to, &edges[i].val);
for (int i = 1; i <= q; i++) {
scanf("%lld", &nodes[i].limit);
nodes[i].pos = i;
}
sort(edges + 1, edges + m + 1);
sort(nodes + 1, nodes + q + 1);
int cur = 1, ru, rv;
for (int cnt = 1; cnt <= q; cnt++) {
for (; cur <= m; cur++) {
if (edges[cur].val <= nodes[cnt].limit) {
ru = findRoot(edges[cur].from);
rv = findRoot(edges[cur].to);
if (ru != rv) {
root[rv] = ru;
num[ru] += num[rv];
}
} else {
cur--;
break;
}
}
long long res = 0;
for (int i = 1; i <= n; i++)
if (root[i] == i)
res += (num[i] * (num[i] - 1));
ans[nodes[cnt].pos] = res;
}
for (int i = 1; i <= q; i++)
printf("%lld\n", ans[i]);
}
return 0;
}