Rezolvare completă PbInfo #1202 Arbvalmax

Se dă un arbore cu N noduri numerotate de la 1 la N cu rădăcina în nodul 1. Fiecare nod din arborele dat are o valoare întreagă atașată. Se dau M întrebări de forma (x, y), unde x este un strămoș al nodului y: dacă s-ar elimina toate nodurile de pe lanțul care unește x cu y (inclusiv nodurile x și y), care ar fi valoarea maximă din nodurile neeliminate?

Cerința

Cunoscând numărul de noduri N, configurația arborelui, valorile atașate celor N noduri, și cele M întrebări, să se răspundă la fiecare întrebare dată.

Date de intrare

Fișierul de intrare arbvalmax.in conține pe prima linie două numere naturale N și M separate printr-un spațiu, reprezentând numărul de noduri ale arborelui, respectiv numărul de întrebări. A doua linie a fișierului conține N-1 numere naturale despărțite prin câte un spațiu. Al i-lea număr de pe această linie reprezintă părintele nodului cu indicele i+1. A treia linie a fișierului conține N numere întregi separate prin câte un spaţiu. Al i-lea număr de pe această linie reprezintă valoarea atașată nodului cu indicele i. Pe următoarele M linii se află câte două numere x, y separate prin câte un spaţiu, reprezentând câte o întrebare de forma descrisă în enunț.

Date de ieșire

Fișierul de ieșire arbvalmax.out va conține, câte unul pe linie, M numere reprezentând răspunsurile pentru cele M întrebări, în ordinea primită în fișierul de intrare.

Restricții și precizări

  • 1 ≤ N, M ≤ 300 000
  • 1 ≤ valoare[i] ≤ 2 000 000 000, pentru orice i, 1 ≤ i ≤ N.
  • 1 ≤ x, y ≤ N Atenție! Nodul x este unul dintre nodurile de pe lanțul 1 – y!
  • Pentru 40% din teste, N ≤ 1000 și M ≤ 10 000.
  • Adâncimea maximă a arborelui nu va depăși valoarea de 100 000.

Exemplu

arbvalmax.in

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

arbvalmax.out

6
10
7

Explicație

Arborele conține următoarele muchii: 1-2, 2-3, 2-4, 1-5, 5-6, 4-7, 5-8.

Pentru prima întrebare, dacă s-ar elimina nodurile de pe lanțul 1-7 (1, 2, 4, 7), nodurile rămase ar fi: 3, 5, 6, 8 și ar avea valorile: 6, 3, 5, 4. Dintre acestea valoarea maximă este 6.

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 Arbvalmax:

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>
#include <cassert>

using namespace std;

ifstream f("arbvalmax.in");
ofstream g("arbvalmax.out");
#define ll long long
#define pb push_back
#define mp make_pair
#define sz size
#define x first
#define y second

#define nmax 1000005
#define inf 2000000002

const int NMAX = 1e6;
const int MMAX = 1e6;
const int VALMAX = 2000000000;

int n, m, val[nmax], with[nmax], withOut[nmax];
vector<int> gf[nmax];
pair< int,int > bestSon[nmax][2];

void citeste(){
    f >> n >> m;

    assert(n >= 1 && n <= NMAX);
    assert(m >= 1 && m <= MMAX);

    for(int i=2; i<=n; ++i){
        int x; f >> x;
        assert(x >= 1 && x <= n);
        gf[x].pb(i);
    }
    for(int i=1; i<=n; ++i){
        f >> val[i];
        assert(val[i] >= 1 && val[i] <= VALMAX);
    }
}

void inJos(int nod){
    for(int i=0; i<(int)gf[nod].sz(); ++i){
        int vc = gf[nod][i];
        inJos(vc);
    }
    pair<int,int> best[2];
    for(int i=0; i<2; ++i) best[i] = mp(-inf, -1);

    for(int i=0; i<(int)gf[nod].sz(); ++i){
        int vc = gf[nod][i];
        if ( best[0].x < max(val[vc], bestSon[vc][0].x) ){
            best[1] = best[0];
            best[0] = mp( max(val[vc], bestSon[vc][0].x), vc );
        }else if ( best[1].x < max( val[vc], bestSon[vc][0].x ) ){
            best[1] = mp( max(val[vc], bestSon[vc][0].x), vc );
        }
    }
    for(int i=0; i<2; ++i){
        bestSon[nod][i] = best[i];
    }
}

void inSus(int nod){
    for(int i=0; i<(int)gf[nod].sz(); ++i){
        int vc = gf[nod][i];
        if ( bestSon[nod][0].y == vc ){
            withOut[vc] = max( withOut[nod], bestSon[nod][1].x );
        }else withOut[vc] = max( withOut[nod], bestSon[nod][0].x );

        if ( bestSon[nod][0].y == vc ){
            with[vc] = max( with[nod], max( val[nod], bestSon[nod][1].x ) );
        }else with[vc] = max( with[nod], max( val[nod], bestSon[nod][0].x ) );

        inSus(vc);
    }
}

void rezolva(){
    inJos(1);
    withOut[1] = -inf; with[1] = -inf;
    inSus(1);

    for(int i=1; i<=m; ++i){
        int nod, tNod;
        f >> tNod >> nod;
        assert(tNod >= 1 && tNod <= n);
        assert(nod >= 1 && nod <= n);
        int ans = max( bestSon[nod][0].x, max( withOut[nod], with[tNod] ) );
        assert(ans >= 1 && ans <= VALMAX);
        g << ans << "
";
    }
}

int main(){
    citeste();
    rezolva();

    f.close();
    g.close();

    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 #1202 Arbvalmax

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1202 Arbvalmax 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!