În perioada Campionatului Mondial din Brazilia se preconizează o creştere a traficului de cafea. Se ştie că sunt N orase, conectate prin N-1 străzi bidirecţionale, astfel încât se poate ajunge din orice oraş în altul. În prezent există K carteluri de cafea aflate în oraşe distincte, care își exercita influența în propriul oraș. Se ştie că fiecare din aceste carteluri doreşte să-şi extindă influenţa în oraşele vecine. Astfel, la un moment de timp, un cartel poate să-şi extindă influenţa într-un oraş vecin doar dacă acesta nu se află sub influenţa altui cartel. O dată ce un cartel îşi extinde influenta asupra unui nou oraş, cartelul îşi poate extinde influenţa şi în oraşele vecine acestuia. Se ştie că până la începerea campionatului mondial, fiecare oraş va fi sub influenţa unui cartel.

ABIN (Agência Brasileira de Inteligência) doreşte să afle în câte moduri poate fi dominată ţara de influenţele celor K carteluri la data începerii campionatului mondial, modulo 666013.

Cerință

Cunoscând numărul de orașe N, modul în care acestea sunt conectate, numărul de carteluri inițiale K și cele K orașe în care se află cartelurile, să se determine numărul de moduri în care ţara poate fi împărţită între cartelurile de cafea, modulo 666013.

Date de intrare

Fișierul de intrare karb.in conține pe prima linie două numere naturale N şi K, reprezentând numărul de oraşe, respectiv numărul cartelurilor existente iniţial. Pe a doua linie din fişier se vor afla K numere, reprezentând oraşele în care se află cele K carteluri. Pe următoarele N-1 linii se vor afla câte două numere naturale, reprezentând o legătură între cele două oraşe.

Date de ieșire

Fișierul de ieșire karb.out va conține pe prima linie un singur număr natural reprezentând numărul de moduri modulo 666013.

Restricții și precizări

1 ≤ K ≤ N ≤ 100 000
Pentru teste în valoare de 10% din punctaj se garantează că k ≤ n ≤ 7, iar pentru alte 20% din teste se garantează că k = 2.
Două oraşe sunt vecine dacă există o stradă bidirecțională între ele.

Exemplu

karb.in

karb.out

Explicație

Cele 5 moduri posibile:

(3) (1, 2, 5) (4, 6)
(3, 1) (2, 5) (4, 6)
(3, 1, 2) (5) (4, 6)
(3, 1) (5) (2, 4, 6)
(3) (5) (1, 2, 4, 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 karb:

//Mihai Popa
//O(n) - 100p

#include<stdio.h>
#include<vector>
#include<algorithm>
#include <cassert>

#define maxdim 200005
#define mod 666013

using namespace std;

int n,k;
int special[maxdim],viz[maxdim],T[maxdim],D[maxdim][2];
vector<int>G[maxdim];

void dfs ( int nod ){
    viz[nod] = 1;
    
    int sons = 0;
    for ( vector<int>::iterator itt = G[nod].begin() ; itt != G[nod].end() ; ++itt ){
        int fiu = *itt;
        if ( viz[fiu] ) continue ;
        
        ++sons; T[fiu] = nod;
        dfs(fiu);
    }
    
    if ( !sons ){
        if ( special[nod] ){
            D[nod][0] = 0,D[nod][1] = 1;
        }
        else{
            D[nod][0] = 1,D[nod][1] = 0;
        }
        return ;
    }
    
    vector<int>localD[2];
    localD[0].resize(sons+1);
    localD[1].resize(sons+1);
    
    localD[0][0] = 1; int ind = 0;
    for ( vector<int>::iterator itt = G[nod].begin() ; itt != G[nod].end() ; ++itt ){
        int fiu = *itt;
        if ( T[fiu] != nod )    continue ;
        
        ++ind;
        localD[0][ind] = (1LL*localD[0][ind-1]*(D[fiu][0]+D[fiu][1]))%mod;
        localD[1][ind] = (1LL*localD[0][ind-1]*D[fiu][1] + 1LL*localD[1][ind-1]*(D[fiu][0]+D[fiu][1]))%mod;
    }
    
    if ( !special[nod] ){
        D[nod][0] = localD[0][ind];
        D[nod][1] = localD[1][ind];
    }
    else{
        D[nod][0] = 0;
        D[nod][1] = localD[0][ind];
    }
}

int main () {
    
    freopen("karb.in","r",stdin);
    freopen("karb.out","w",stdout);
    
    scanf("%d %d",&n,&k);
    assert(n >= 1 && n <= 200000);
    assert(k >= 1 && k <= n);
    int x,y;
    for ( int i = 1 ; i <= k ; ++i ){
        scanf("%d",&x);
        assert(!special[x]);
        assert(x >= 1 && x <= n);
        special[x] = x;
    }
    for ( int i = 1 ; i < n ; ++i ){
        scanf("%d %d",&x,&y);
        assert(x >= 1 && x <= n);
        assert(y >= 1 && y <= n);
        assert(x != y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    
    dfs(1);
    
    printf("%d
",D[1][1]);
    
    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 #1116 karb

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