Colorazione dell'albero#11002

Colorazione dell'albero (Editoriale)

Il numero di punti ottenuti è univocamente determinato dal primo vertice scelto. Pertanto, è sufficiente esaminare tutti i possibili vertici di partenza, calcolare per ciascuno di essi il numero finale di punti e scegliere il valore massimo.

Eseguiamo una ricerca in profondità a partire dal vertice $1$ e calcoliamo il valore $w e i g h t [v]$ weight[v] — la dimensione del sottoalbero con radice nel vertice $v$ (cioè il numero di vertici nel sottoalbero di $v$ ). Siano $t o_{1}, t o_{2}, ..., t o_{k}$ to_1, to_2, ..., to_k i figli di $v$ . Allora vale la formula:

w e i g h t [v] = 1 + w e i g h t [t o_{1}] + w e i g h t [t o_{2}] + ... + w e i g h t [t o_{k}]

weight[v] = 1 + weight[to_1] + weight[to_2] + ... + weight[to_k]

Il secondo attraversamento in profondità viene eseguito su tutti i vertici e permette di ricalcolare il numero massimo di punti che si possono ottenere se si inizia la partita da un dato vertice.

Consideriamo la funzione dfs2. Supponiamo di trovarci nel vertice $v$ , e che il suo genitore sia il vertice $p$ . Se come primo passo viene scelto il vertice $v$ , allora il numero di punti ottenuti è uguale a $s$ .

v o i d df s 2 (in t v, in tp, l o n g l o n g s)

void~dfs2(int~v,~int p,~long~long~s)

Eseguiamo la transizione lungo l'arco $(v, t o)$ (v, to) e mostriamo come calcolare la risposta se si inizia la partita dal vertice $t o$ . In sostanza, stiamo eseguendo un ri-radicamento dell'albero: la radice viene spostata dal vertice $v$ al vertice $t o$ .

A sinistra è raffigurato l'albero con radice in $v$ . Il vertice $t o$ è uno dei suoi discendenti, e $p$ — il suo predecessore. A destra è mostrato l'albero con radice in $t o$ .

Per calcolare $w e i g h t [t o]$ weight[to] per l'albero di destra, è necessario sottrarre dal valore $s$ dell'albero di sinistra $w e i g h t [t o]$ weight[to] dell'albero di sinistra e aggiungere il numero di vertici nella regione indicata dalla linea tratteggiata. Questo numero è uguale a $n - w e i g h t [t o]$ n - weight[to].

Esempio

Supponiamo che il primo vertice scelto sia $1$ . Allora il numero di punti ottenuti sarà $25$ .

Se il primo vertice scelto fosse $2$ , il numero di punti ottenuti sarebbe $26$ . Eseguiamo la transizione dal vertice $1$ al vertice $2$ nel modo seguente: sottraiamo da $s = 25$ s = 25 il valore $w e i g h t [2] = 4$ weight[2] = 4 e aggiungiamo $(9 - w e i g h t [4]) = 5$ (9 - weight[4]) = 5. Di conseguenza otteniamo $25 - 4 + 5 = 26$ 25 - 4 + 5 = 26, il valore di $s$ per l'albero con radice nel vertice $2$ .

Il numero massimo di punti è uguale a $36$ e si ottiene se si inizia la partita dal vertice $7$ .

Esercizio

Consideriamo il seguente albero:

Supponiamo che come primo passo venga scelto il vertice $1$ . Trovate il numero di punti ottenuti.
Spostate la radice dal vertice $1$ al vertice $3$ e calcolate il numero di punti ottenuti.
Successivamente spostate la radice da $3$ a $4$ , da $3$ a $5$ e da $3$ a $6$ . Risolvete ciascuno dei problemi ottenuti.

Implementazione dell'algoritmo

Dichiariamo la lista di adiacenza del grafo $g$ .

vector<vector<int>> g;
vector<int> weight;

La funzione dfs1 esegue una ricerca in profondità a partire dal vertice $v$ , il cui genitore è il vertice $p$ . In questo caso viene calcolato $w e i g h t [v]$ weight[v] — la dimensione del sottoalbero con radice nel vertice $v$ , cioè il numero di vertici in questo sottoalbero.

void dfs1(int v, int p)
{
  weight[v] = 1;
  for (int to : g[v])
    if (to != p)
    {
      dfs1(to, v);
      weight[v] += weight[to];
    }
}

C++

La funzione dfs2 esegue una ricerca in profondità a partire dal vertice $v$ , il cui genitore è il vertice $p$ . Se come primo passo della partita viene scelto il vertice $v$ , allora il numero di punti ottenuti sarà $s$ .

void dfs2(int v, int p, long long s)
{
  res = max(res, s);
  for (int to : g[v])
    if (to != p) dfs2(to, v, s - weight[to] + n - weight[to]);
}

Parte principale del programma. Leggiamo i dati in input. Costruiamo il grafo.

scanf("%d", &n);
g.resize(n + 1);
weight.resize(n + 1);
for (i = 1; i < n; i++)
{
  scanf("%d %d", &a, &b);
  g[a].push_back(b);
  g[b].push_back(a);
}

C++

Avviamo la ricerca in profondità a partire dal vertice $1$ .

dfs1(1, 0);

Nella variabile $s$ calcoliamo la somma di tutti i numeri nell'array $w e i g h t$ weight. Questo valore è uguale al numero di punti ottenuti nel caso in cui venga scelto per primo nella partita il vertice $1$ .

s = 0;
for (i = 1; i <= n; i++)
  s += weight[i];

Avviamo la seconda ricerca in profondità a partire dal vertice $1$ .

dfs2(1, 0, s);

Stampiamo la risposta.

printf("%lld\n", res);