Zadanie distance in the tree Codeforces

Question

Mam problem z takim zadaniem: https://codeforces.com/contest/161/problem/D

Nie wiem jak je zrobić innaczej niż w O(N^2) puszczając się z każdego wierzchołka DFS-em / BFS-em. Pewnie wejdzie coś w O(N*K), może np. jakiś dynamik, tylko nie wiem jak to zrobić.

Z góry dziękuję za pomoc i poświęcony czas!

Answer 1

Standardowe dp na drzewie. dp[v][k] to liczba scieżek długości k w poddrzewie v zaczynających się w v. Jak policzyć wynik znając to dp?

Comments

a jak policzymy tą ścieżkę za pomocą tego dp?

Zakładam, że ukorzeniamy drzewo w jedynce, a szukana ścieżka to długości 2, pomarańczowa.

---

Jeśli ten wierzchołek pod 1 to 2, ten na lewo to 3, a na prawo to 4 to łatwo policzyć znając dp 3 i 4. Basically, szukasz liczby ścieżek długości 0 wychodzących z 3 i 4 co jest policzone w dp[3][0] i dp[4][0]

---

A to nie wejdzie O(N*K^2)?

---

Dlaczego? Mi się wydaje, że O(NK) wejdzie

---

Jak policzyć dp[2][3] ?

---

W tym przypadku to 0. Pamiętaj, że dp[2][3] to liczba ścieżek zaczynających się w 2 i będących w poddrzewie 2

---

Ale ścieżki 5->2->3 nie policzymy chyba nigdy, jak ukorzenimy drzewo w jedynce. Chyba nie dokońca to rozumiem.

---

Algorytm ma 2 fazy. Na początku liczymy wszystkie dp. Potem liczymy wynik na podstawie tego dp. Widzisz jak policzyć samo dp?

---

dp[v][i], to suma po dp dzieci, dokładnie: dp[dziecko_v][i-1] ?

---

Tak. No to teraz załózmy że ścieżka długości k przechodzi przez wierzchołek v i znajduje się w całości w jego poddrzewie. Jak policzyć liczbe takich scieżek?

---

Można się przeiterować po wszystkich wierzchołkach i wyn += dp[v][1] + dp[v][k-1] + dp[v][2] + dp[v][k-2] + dp[v][3] + dp[v][k-3].... ?

---

nie, to bez sensu chyba jednak.

---

Prawie, tylko czy tam na pewno powinno być dodawanie?

---

Przeszło na 100pkt.

Wsm trzeba teraz zauważyć, to co ty zapewne zauważyłeś(po to liczyliśmy to dp), że zakładamy, że jakaś ścieżka zaczyna się w wierzchołku v, i bierzemy każde możliwości wzięcia z poddrzew. Co ciekawe tam są 3 fory, ale złożonnośc się amortyzuje, bo pętla po f wykona się maksymalnie N razy. (dla danego i dokładnie raz). Faktycznie O(N*K).

Kod: 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
typedef long long ll;

int n = 0, k = 0, a = 0, b = 0;
ll wyn = 0;
vector<vector<int>> krawedzie;
vector<vector<ll>> dp;
vector<int> parent;

void DFS(int v, int rodzic)
{
    parent[v] = rodzic;
    for (int i = 0; i < krawedzie[v].size(); ++i)
    {
        int wierz = krawedzie[v][i];
        if (wierz != rodzic)
            DFS(wierz,v);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k;

    krawedzie.assign(n+1,{});
    for (int i = 0; i < n-1; ++i)
    {
        cin >> a >> b;
        krawedzie[a].push_back(b);
        krawedzie[b].push_back(a);
    }

    parent.assign(n+1,0);
    DFS(1,0);

    dp.assign(n+1,{});
    for (int i = 1; i <= n; ++i)
        dp[i].assign(k+1,0);

    for (int i = 1; i <= n; ++i)
        dp[i][0] = 1;

    for (int i = 1; i <= k; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            for (int f = 0; f < krawedzie[j].size(); ++f)
            {
                int wierz = krawedzie[j][f];
                if (wierz != parent[j])
                    dp[j][i] += dp[wierz][i-1];
            }
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j <= k / 2; ++j)
        {
            int dl_1 = j, dl_2 = k - j, ile_dzieci = krawedzie[i].size();
            if (i != 1)
                ile_dzieci--;
            if (ile_dzieci == 0)
                continue;
            else if (ile_dzieci == 1)
            {
                if (dl_2 == k)
                    wyn += dp[i][k];
            }
            else if (dl_1 == 0)
                wyn += dp[i][dl_2];
            else
            {
                ll suma = 0;
                for (int f = 0; f < krawedzie[i].size(); ++f)
                {
                    int wierz = krawedzie[i][f];
                    if (wierz == parent[i])
                        continue;
                    suma += dp[wierz][dl_2 - 1];
                }
                ll dod = 0;
                for (int f = 0; f < krawedzie[i].size(); ++f)
                {
                    int wierz = krawedzie[i][f];
                    if (wierz == parent[i])
                        continue;
                    dod += dp[wierz][dl_1-1] * (suma - dp[wierz][dl_2-1]);
                }
                if (dl_1 == dl_2)
                    wyn += dod / 2;
                else
                    wyn += dod;
            }
        }
    }

    cout << wyn << '\n';

    return 0;
}

Znasz jeszcze jakieś fajne zadania na dp na drzewie? 

Dzięki za pomoc! 

---

Inne zadanie to np. Wakacje Bajtazara

---

@pasjonat_algorytmiki, 

Też fajne zadanie to parada z finału XXIII OI. Raczej łatwiejsze od tego distance in the tree.