Compania lui Jimmy are n plantații cu flori. Pentru fiecare plantație se cunoaște tipul florilor cultivate, respectiv câte tone de flori au fost produse anul acesta. Se cunoaște că plantațiile cu flori sunt conectate prin n - 1 drumuri astfel încât la fiecare plantație se poate ajunge de la oricare altă plantație și există un singur mod de ajunge de la plantația x la plantația y , pentru fiecare 1 ≤ x, y ≤ n. De asemenea, știm și distanța în km pentru fiecare dintre cele n - 1 drumuri.

Cerința

Jimmy vrea să aducă toate florile de același tip în același loc, cu cost minim de transport. Dacă avem a tone de flori şi vrem să le trimitem pe o distanță de b kilometri, costul transportului este a * b. Pentru fiecare tip de floare Jimmy vrea să determine costul minim de transport pentru a aduce toate florile de același tip la un loc.

Date de intrare

Pe prima linie se va găsi numărul n, apoi, pe cea de-a doua linie, n litere mici separate între ele prin câte un spațiu, care simbolizează tipul de floare produs pe plantația i (fiecare tip de floare este o literă mică a alfabetului englez). Pe cea de-a treia linie se găsesc n numere întregi care reprezintă câte tone din fiecare floare au fost produse pe plantația i. Pe fiecare dintre următoarele n - 1 linii se găsesc trei numere naturale x, y, d, cu semnificația că există drum direct între plantațiile x şi y, iar numărul d reprezintă distanța de la x la y.

Date de ieșire

Pe prima linie se afișează 26 de numere separate prin spațiu, al i-lea număr reprezentând costul minim de transport pentru tipul de floare specificat de litera de pe poziția i în alfabetul englez (răspunsurile sunt în ordinea în care literele se găsesc în alfabet).

Restricții și precizări

4 ≤ n < 200 001.
Fiecare dintre numerele din datele de intrare este un număr natural mai mic decât 200 001.
Destinaţia finală a fiecărui transport este una dintre cele n plantaţii existente.
Dacă există litere care nu reprezintă codul tipului unei flori, atunci costul minim de transport pentru acel tip este 0.
Pentru 20% din teste, n < 1000.
Pentru alte 25% din teste, n < 100 000.

Exemplu

Intrare

Ieșire

8 33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema flori4:

#include <bits/stdc++.h>
#define DIM 200010

using namespace std;

vector < pair<long long, long long> > L[DIM];
char t[DIM], C;
long long v[DIM], D[DIM][2], Sol[DIM], S[DIM], J[DIM];
bitset <DIM> f;
long long n, i, x, y, c, sol;
long long Total[130];

void dfs(long long nod) {
    f[nod] = 1;

    D[nod][1] = 0;  /// numarul minim de noduri eliminate sa rezolv subarborele lui nod
                    /// si nod sa ramana
    D[nod][0] = 1;
    for (long long i=0;i<L[nod].size(); i++) {
        long long vecin = L[nod][i].first;
        long long cost = L[nod][i].second;
        if (f[vecin] == 0) {
            dfs(vecin);
            D[nod][1] += D[vecin][0];
            D[nod][0] += min(D[vecin][0], D[vecin][1]);
        }
    }
}

void dfs1(long long nod) {
    f[nod] = 1;

    if (t[nod] == C)
        S[nod] = v[nod];
    else
        S[nod] = 0;
    J[nod] = 0;
    for (long long i=0;i<L[nod].size(); i++) {
        long long vecin = L[nod][i].first;
        long long cost = L[nod][i].second;
        if (f[vecin] == 0) {
            dfs1(vecin);
            S[nod] += S[vecin];
            J[nod] += J[vecin] + S[vecin] * cost;
        }
    }
}

void dfs2(long long nod, long long tata, long long cst) {
    f[nod] = 1;
    if (nod != 1)
        J[nod] = J[tata] - S[nod] * cst + (Total[C] - S[nod]) * cst;

    sol = min(sol, J[nod]);

    for (long long i=0;i<L[nod].size(); i++) {
        long long vecin = L[nod][i].first;
        long long cost = L[nod][i].second;
        if (f[vecin] == 0) {
            dfs2(vecin, nod, cost);

        }
    }
}

int main () {

    cin>>n;
    for (i=1;i<=n;i++) {
        cin>>t[i];

    }

    for (i=1;i<=n;i++) {
        cin>>v[i];
        Total[t[i]] += v[i];
    }

    for (i=1;i<n;i++) {
        cin>>x>>y>>c;
        L[x].push_back(make_pair(y, c));
        L[y].push_back(make_pair(x, c));
    }
    f.reset();

    for (C='a'; C <= 'z'; C++) {
        if (Total[C] == 0) {
            Sol[C] = 0;
            continue;
        }
        f.reset();
        dfs1(1);
        f.reset();
        sol = 10000000000000000LL;
        dfs2(1, 0, 0);
        Sol[C] = sol;

    }

    for (i='a'; i<='z'; i++)
        cout<<Sol[i]<<" ";
    cout<<"\n";
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2539 flori4

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2539 flori4 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2539 flori4