codeforces 1108 F MST 통일 차 작은 생 성 트 리 lca

F. MST Unification
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given an undirected weighted connected graph with nn vertices and mm edges without loops and multiple edges.
The ii-th edge is ei=(ui,vi,wi)ei=(ui,vi,wi); the distance between vertices uiui and vivi along the edge eiei is wiwi (1≤wi1≤wi). The graph is connected, i. e. for any pair of vertices, there is at least one path between them consisting only of edges of the given graph.
A minimum spanning tree (MST) in case of positive weights is a subset of the edges of a connected weighted undirected graph that connects all the vertices together and has minimum total cost among all such subsets (total cost is the sum of costs of chosen edges).
You can modify the given graph. The only operation you can perform is the following: increase the weight of some edge by 11. You canincrease the weight of each edge multiple (possibly, zero) times.
Suppose that the initial MST cost is kk. Your problem is to increase weights of some edges with minimum possible number of operationsin such a way that the cost of MST in the obtained graph remains kk, but MST is unique (it means that there is only one way to choose MST in the obtained graph).
Your problem is to calculate the minimum number of operations required to do it.
Input
The first line of the input contains two integers nn and mm (1≤n≤2⋅105,n−1≤m≤2⋅1051≤n≤2⋅105,n−1≤m≤2⋅105) — the number of vertices and the number of edges in the initial graph.
The next mm lines contain three integers each. The ii-th line contains the description of the ii-th edge eiei. It is denoted by three integers ui,viui,vi and wiwi (1≤ui,vi≤n,ui≠vi,1≤w≤1091≤ui,vi≤n,ui≠vi,1≤w≤109), where uiui and vivi are vertices connected by the ii-th edge and wiwi is the weight of this edge.
It is guaranteed that the given graph doesn't contain loops and multiple edges (i.e. for each ii from 11 to mm ui≠viui≠vi and for each unordered pair of vertices (u,v)(u,v) there is at most one edge connecting this pair of vertices). It is also guaranteed that the given graph is connected.
Output
Print one integer — the minimum number of operations to unify MST of the initial graph without changing the cost of MST.
Examples
input
Copy

8 10
1 2 1
2 3 2
2 4 5
1 4 2
6 3 3
6 1 3
3 5 2
3 7 1
4 8 1
6 2 4

output
Copy

1

input
Copy

4 3
2 1 3
4 3 4
2 4 1

output
Copy

0

input
Copy

3 3
1 2 1
2 3 2
1 3 3

output
Copy

0

input
Copy

3 3
1 2 1
2 3 3
1 3 3

output
Copy

1

input
Copy

1 0

output
Copy

0

input
Copy

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

output
Copy

2

그림 을 지정 합 니 다. 하나의 작업 은 하나의 가중치 에 하 나 를 더 하 는 것 입 니 다. 최소 몇 번 의 작업 을 통 해 최소 생 성 트 리 가 유일한 것 입 니 다.
작은 생 성 트 리 의 가중치 가 최소 생 성 트 리 보다 크 더 라 도 최소 생 성 트 리 를 만 든 후 이 최소 생 성 트 리 에 없 는 사 이 드 를 매 거 진 추가 합 니 다. 이때 링 이 형성 되 고 이 링 의 최대 치 변 이 새로 추 가 된 사 이 드 와 같 으 면 가장 작은 생 성 트 리 가 유일한 것 이 아니 므 로 새로 추 가 된 사 이 드 에서 한 번 조작 해 야 합 니 다.

#include 
#include 
#include 
#include 
using namespace std;
const int N = 2e5 + 10;
struct edge {
    int u, v, w, use;
};
struct eop {
    bool operator() (const edge& a, const edge& b)const {
        return a.w < b.w;
    }
};
vector es;
vector G[N];
int n, m, p[N], fa[N][25], mcost[N][25], cost[N], depth[N];

int find(int v) {
    if (p[v] == v) return v;
    return p[v] = find(p[v]);
}

void dfs(int u, int f) {
    depth[u] = depth[f] + 1;
    p[u] = f;
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i].v;
        int w = G[u][i].w;
        if (v == f) continue;
        cost[v] = w;
        //printf("---%d %d
", v, u);
        dfs(v, u);
    }
}

void process() {
    for (int i = 1; i <= n; i++) {
        fa[i][0] = p[i];
        mcost[i][0] = cost[i];
    }
    for (int k = 1; (1 << k) <= n; k++)
        for (int i = 1; i <= n; i++) {
            if (fa[i][k - 1] != 0) {
                fa[i][k] = fa[fa[i][k - 1]][k - 1];
                mcost[i][k] = max(mcost[i][k - 1], mcost[fa[i][k - 1]][k - 1]);
            }
        }
}

int query(int u, int v) {
    int ans = 0;
    if (depth[u] < depth[v]) swap(u, v);
    for (int i = 20; i >= 0; i--) {
        if (depth[u] - (1 << i) >= depth[v]) {
            ans = max(ans, mcost[u][i]);
            u = fa[u][i];
        }
    }
    if (u == v) return ans;
    for (int i = 20; i >= 0; i--) {
        if (fa[u][i] != 0 && fa[u][i] != fa[v][i]) {
            ans = max(mcost[u][i], ans);
            ans = max(mcost[v][i], ans);
            u = fa[u][i]; v = fa[v][i];
        }
    }
    ans = max(ans, cost[u]);
    ans = max(ans, cost[v]);
    return ans;
}

int main() {
    scanf("%d%d", &n, &m);
    int u, v, w;
    memset(fa, 0, sizeof(fa));
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &u, &v, &w);
        es.push_back({u, v, w, 0});
    }
    for (int i = 1; i <= n; i++) p[i] = i;
    sort(es.begin(), es.end(), eop());
    for (int i = 0; i < es.size(); i++) {
        u = es[i].u; v = es[i].v, w = es[i].w;
        int fu = find(u), fv = find(v);
        if (fu != fv) {
            p[fu] = fv;
            G[u].push_back({u, v, w, 0});
            G[v].push_back({v, u, w, 0});
            es[i].use = 1;
        }
    }
    depth[0] = 0;
    cost[1] = 0;
    dfs(1, 0);
    process();

    int ans = 0;
    for (int i = 0; i < es.size(); i++) {
        if (es[i].use) continue;
       // printf ("%d %d %d %d
", es[i].u, es[i].v, es[i].w, query(es[i].u, es[i].v));
        if (query(es[i].u, es[i].v) == es[i].w) ans ++;
    }
    printf("%d
", ans);
    return 0;
}