并查集学习

参考

CITY

Example

input

1
5 5 3
1 2 2
2 3 3
3 4 1
4 5 1
5 1 3
3
2
1

output

2
6
10

 思路：离线并查集

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>
#include <map>
#include <set>
using namespace std;
#define mst(x, y) memset(x, y, sizeof x);
#define X first
#define Y second
#define int long long
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 200010, INF = 0x3f3f3f3f, EPS = 1e-8;
typedef pair<int, int> PII;
int n, m, Q, t;
int ans[N];
int p[N];
int cnt[N];
struct Node
{
    int l, r, w;
} node[N];
struct QUE
{
    int id, c;
} que[N];
bool cmp1(Node a, Node b)
{
    return a.w > b.w;
}
bool cmp2(QUE a, QUE b)
{
    return a.c > b.c;
}
int find(int x) // 并查集
{
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}

signed main()
{
    FAST;
    cin >> t;
    while (t--)
    {
        cin >> n >> m >> Q;
        for (int i = 1; i <= n; i++)
        {
            p[i] = i;
            cnt[i] = 1;
        }

        for (int i = 1, a, b, c; i <= m; i++)
        {
            cin >> a >> b >> c;
            node[i] = {a, b, c};
        }
        for (int i = 1, a; i <= Q; i++)
        {
            cin >> a;
            que[i] = {i, a};
        }

        sort(node + 1, node + 1 + m, cmp1);
        sort(que + 1, que + 1 + Q, cmp2);

        int j = 1, sum = 0;
        for (int i = 1; i <= Q; i++)
        {
            int q = que[i].c, id = que[i].id;

            while (j <= m && node[j].w >= q)
            {
                int pa = find(node[j].l), pb = find(node[j].r);
                if (pa != pb)
                {
                    sum += cnt[pa] * cnt[pb];
                    p[pa] = pb;
                    cnt[pb] += cnt[pa];
                }
                j++;
            }
            ans[id] = sum;
        }
        for (int i = 1; i <= Q; i++)
        {
            cout << ans[i] << endl;
        }
    }
    system("pause");
    return 0;
}