# PBinfo #1974 – TrumpLandia – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

După o confruntare eroică, Trump a fost ales democratic președintele unei republici prospere, TrumpLandia. Natural, prima sa prioritate e să construiască o rețea de buncăre, pentru a veni în întâmpinarea unui atac al vecinilor imperaliști.
N buncăre au fost deja construite. Trump trebuie să aleagă între M posibile rute bidirecționale pentru a le conecta. Un plan de conectare este alcătuit dintr-un subset minim de astfel de legături, astfel încât din fiecare locație să se poată ajunge în orice altă locație. Costul unui plan este dat de suma distanțelor legăturilor.

Deoarece rutele sunt vulnerabile la bombardamente aeriene, Trump vă cere să estimați un plan de cost minim. În plus, Trump vă cere să calculați Q soluții de rezervă, pentru situația în care una dintre cele M legături este sigur inclusă în plan.

Date de intrare
Datele de intrare vor fi citite din fișierul trumplandia.in. Pe prima linie se află trei numere separate prin spațiu: N (numărul de buncăre), M (numărul de rute posibile), Q (numărul de soluții de rezervă). 
Pe următoarele M linii se află triplete de forma (nod1, nod2, dist12) ce descriu o posibilă legătură între nodurile nod1 și nod2 cu distanța dist12. 
Pe următoarele Q linii se află câte un număr Qi, reprezentând indexul unei muchii care trebuie inclusă într-un plan de rezervă. (valorile se pot repeta)

Date de ieșire
Datele de ieșire vor fi afișate în fișierul trumplandia.out. 
Pe prima linie se va afla un număr reprezentând costul celui mai bun plan, pentru situația în care pot fi folosite oricare dintre cele M rute. 
Pe următoarele Q linii se află un număr Ci reprezentând costul minim al unui plan care conține muchia Qi.

Restricții și precizări

1 ≤ N ≤ 200.000 (pentru 30% din teste N ≤ 1000)
N-1 ≤ M ≤ 200.000 (pentru 30% din teste M ≤ 1000)
1 ≤ Q ≤ 300.000 (pentru 30% din teste Q ≤ 1000)
distanța asociată unei rute este o valoare întreagă din intervalul [1, 1.000.000.000].

ATENȚIE!!! Între oricare două buncăre pot exista MAI MULTE rute de distanțe diferite sau nu. Exemplu: (1 2 4) și (1 2 6) sunt două muchii între buncărele 1 și 2 de distanțe 4, respectiv 6.

Exemplu:
trumplandia.in

6 8 8
1 2 4
4 1 6
3 1 2
2 3 3
5 2 4
3 4 3
4 5 5
5 6 1
1
2
3
4
5
6
7
8
trumplandia.out

13
14
16
13
13
13
13
14
13
Explicație

## Cod sursă C++

```cpp
/* autor: Radu Stochitoiu */
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <map>
#define MAXN 2000001
using namespace std;
int TT[MAXN], RG[MAXN], n, m, q, i, j, new_father, x_tmp, y_tmp, k, K, start;
int Tata_Sus[MAXN << 1], cost_intern[MAXN << 1];
int  dist, l, sol, pos, a, b, R, y,h=300;
long long cost;
vector <int> G[MAXN << 1];
int T[MAXN], L[MAXN], T2[MAXN];
struct elem {
    int x, y, c;
} P[MAXN], P_backup[MAXN];
int cmp(elem a, elem b) {
    return (a.c < b.c);
}
void dfs(int nod,int tata,int niv)
{
    T2[nod]=tata;L[nod]=niv;
    if(niv % h == 0) tata=nod;
    for(int i = 0; i < G[nod].size(); ++i)
        {
            dfs(G[nod][i], tata, niv+1);
            T[G[nod][i]]=nod;
        }
}
int lca(int x, int y)
{
    while (T2[x]!=T2[y])
    {
        if(L[x] > L[y]) x=T2[x];
            else y=T2[y];
    }
    while(x != y)
    {
        if(L[x] > L[y]) x=T[x];
            else y=T[y];
    }
    return x;
}
int find(int x)
{
    for(R = x; R != TT[R]; R = TT[R]);
    // realizam compresia drumurilor
    while(TT[x] != x)
    {
        y = TT[x];
        TT[x] = R;
        x = y;
    }
    return R;
}
void unite(int x, int y)
{
    // retinem noul tata pentru reprezentarea in arborele noduri-muchii
    // actualizam tatal si rangul
    if(RG[x] > RG[y]) TT[y] = x, new_father = x;
    else {
        if(RG[x] == RG[y])
            RG[y] ++;
        TT[x] = y, new_father = y;
    }
}
int main() {
    freopen("trumplandia.in", "r", stdin);
    freopen("trumplandia.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &q);
    for(i = 1; i <= n; ++i) {
        // initial fiecare nod este propriul sau tata si rangul fiecarei
        // multimi disjuncte este 1
        RG[i] = 1;
        TT[i] = i;
        Tata_Sus[i] = i;
    }
    for(i = 1; i <= m; ++i) {
        // citim muchiile si le salvam pentru cand vom avea nevoie de ele
        // la query-uri
        scanf("%d%d%d", &P[i].x, &P[i].y, &P[i].c);
        P_backup[i] = P[i];
    }
    // sortam muchiile
    sort(P + 1, P + m +1, cmp);
    k = n;
    for(i = 1; i <= m; ++i)
    {
        // gasim cel mai inalt nod din reprezentarea multii disjuncte (Kruskal)
        x_tmp = find(P[i].x);
        y_tmp = find(P[i].y);
        // daca sunt in multimi diferite unim multimile
        if(x_tmp != y_tmp) {
            unite(x_tmp, y_tmp);
            // actualizam costul
            cost += P[i].c;
            // actualizam listele de vecini pentru arborele noduri-muchii
            G[++k].push_back(Tata_Sus[x_tmp]);
            G[k].push_back(Tata_Sus[y_tmp]);
            Tata_Sus[new_father] = k;
            // mapam muchia la costul acesteia
            cost_intern[k] = P[i].c;
        }
    }
    printf("%lld\n", 1LL * cost);
    // aplicam rmq pentru query-uri in O(1)
    dfs(k,0, 0);
    while(q--) {
        scanf("%d", &i);
        // aplicam LCA si aflam costul noului arbore
        printf("%lld\n", 1LL*(cost + P_backup[i].c - cost_intern[lca(P_backup[i].x, P_backup[i].y)]));
    }
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1974)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1974/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1974/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)