Problem-Solving/17398.cpp at master · Eastplanet/Problem-Solving · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include <string>
#include <math.h>

using namespace std;

typedef pair<int, int>P;

P connect[100001];
int disconnect[100001];
int linearDisconnect[100001];

int u[100001];

int find(int a) {
    if (u[a] < 0)return a;
    return u[a] = find(u[a]);
}

unsigned long long merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b)return 0;
    if (u[a] < u[b]) {
        int temp = u[a];
        int temp2 = u[b];
        u[a] += u[b];
        u[b] = a;
        return (unsigned long long)temp * (unsigned long long)temp2;
    }
    else {
        int temp = u[a];
        int temp2 = u[b];
        u[b] += u[a];
        u[a] = b;
        return (unsigned long long)temp * (unsigned long long)temp2;
    }
}


int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int N, M, Q; cin >> N >> M >> Q;

    fill(&u[0], &u[100001], -1);


    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        connect[i + 1] = P{ a,b };
    }

    for (int i = 0; i < Q; i++) {
        int temp; cin >> temp;
        linearDisconnect[i] = temp;
        disconnect[temp] = 1;
    }

    for (int i = 1; i <= M; i++) {
        if (disconnect[i] == 1)continue;

        merge(connect[i].first, connect[i].second);
    }

    unsigned long long sum = 0;

    for (int i = Q - 1; i >= 0; i--) {
        int idx = linearDisconnect[i];
        unsigned long long val = merge(connect[idx].first, connect[idx].second);
        sum += val;
    }

    cout << sum;

}