Yolların yaxşılaşdırılması#10684

Yolların yaxşılaşdırılması (Həll təhlili)

$f (v)$ funksiyası vasitəsilə $v$ zirvəsi köklü olan alt ağacda yolların keyfiyyətini yaxşılaşdırmağın neçə üsulu olduğunu bildirək. $t o$ ilə $v$ zirvəsinin övladını işarə edək.

Əgər $(v, t o)$ (v, to) yolu pis qalırsa, onda kökü $t o$ zirvəsi olan alt ağacın bütün yolları yaxşılaşdırılmalıdır.
Əgər $(v, t o)$ (v, to) yolunu yaxşılaşdırsaq, onda kökü $t o$ zirvəsi olan alt ağacda yolların keyfiyyətini yaxşılaşdırmağın üsullarının sayı $f (t o)$ -ya bərabərdir.

Tutaq ki, $t o_{1}, t o_{2}, ..., t o_{k}$ to_1, to_2, ..., to_k — $v$ -nin övladlarıdır. O zaman

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)

Əgər $v$ yarpaqdırsa (övladı olmayan zirvə), onda $f (v) = 1$ f(v) = 1 qoyaq.

Nümunə

Şərtdə verilmiş nümunələri nəzərdən keçirək. Hər bir $v$ zirvəsi üçün $f (v)$ qiymətini yazacağıq.

Birinci nümunədə yolların keyfiyyətini yaxşılaşdırmağın $4$ üsulu mövcuddur ki, bu da hər hansı bir şəhərdən $1$ -ə qədər olan yolda ən çoxu bir pis yolun mövcud olduğu vəziyyətləri təmsil edir. Pis yollar qırıq xəttlərlə, yaxşı yollar isə dəstəklərlə göstərilib.

Alqoritmin tətbiqi

Bütün hesablama əməliyyatları $M O D = 1 0^{9} + 7$ MOD = 10^9 + 7 moduluna əsasən həyata keçirilir.

#define MOD 1000000007

dfs funksiyası $v$ zirvəsi köklü olan alt ağacda yolların keyfiyyətini yaxşılaşdırmağın neçə üsulu olduğunu bildirən $f (v)$ funksiyasının qiymətini hesablayır. $v$ zirvəsinin əcdadı $p$ olur.

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

Əgər $t o_{1}, t o_{2}, ..., t o_{k}$ to_1, to_2, ..., to_k — $v$ -nin övladlarıdırsa, onda

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++

Giriş məlumatlarını oxuyuruq. Ağacı qururuq.

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++

Nəticəni hesablamaq və çıxışa vermək.

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