Покращення доріг#10684

Покращення доріг (Розбір)

Нехай $f (v)$ — кількість способів покращити якість доріг для піддерева з коренем у вершині $v$ . Позначимо через $t o$ сина вершини $v$ .

Якщо дорога $(v, t o)$ (v, to) залишається поганою, то всі дороги в піддереві з коренем у вершині $t o$ повинні бути покращені.
Якщо дорогу $(v, t o)$ (v, to) покращити, то кількість способів покращити якість доріг для піддерева з коренем у вершині $t o$ дорівнює $f (t o)$ .

Нехай $t o_{1}, t o_{2}, ..., t o_{k}$ to_1, to_2, ..., to_k — сини $v$ . Тоді

f (v) = (f (t o_{1}) + 1) \cdot (f (t o_{2}) + 1) \cdot ... \cdot (f (t o_{k}) + 1)

f(v) = (f(to_1) + 1) \cdot (f(to_2) + 1) \cdot ... \cdot (f(to_k) + 1)

Якщо $v$ — листок (вершина, яка не має синів), то покладемо $f (v) = 1$ f(v) = 1.

Приклад

Розглянемо приклади, наведені в умові. Для кожної вершини $v$ запишемо значення $f (v)$ .

У першому прикладі існує $4$ способи покращити якість доріг, при яких на шляху від міста $1$ до будь-якого іншого міста є не більше однієї поганої дороги. Погані дороги позначені пунктирними лініями, а хороші — суцільними.

Реалізація алгоритму

Всі обчислення виконуються по модулю $M O D = 1 0^{9} + 7$ MOD = 10^9 + 7.

#define MOD 1000000007

Функція dfs обчислює значення $f (v)$ — кількість способів покращити якість доріг для піддерева з коренем у вершині $v$ . Предком $v$ є вершина $p$ .

long long dfs(int v, int p = -1)
{
  long long s = 1;

Якщо $t o_{1}, t o_{2}, ..., t o_{k}$ to_1, to_2, ..., to_k — сини $v$ , то

f (v) = (f (t o_{1}) + 1) \cdot (f (t o_{2}) + 1) \cdot ... \cdot (f (t o_{k}) + 1)

f(v) = (f(to_1) + 1) \cdot (f(to_2) + 1) \cdot ... \cdot (f(to_k) + 1)

  for (int to : g[v])
    if (to != p)
    {
      long long sub = dfs(to, v);
      s = (s * (sub + 1)) % MOD;
    }
  return s;
}

C++

Читаємо вхідні дані. Будуємо дерево.

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

C++

Обчислюємо і виводимо результат.

res = dfs(1);
printf("%lld\n", res);