Nice triplets

#include<iostream>
#include<vector>

using namespace std;

int64_t n;
void dfs1(const vector<vector<int>> &edges, vector<vector<int64_t>> &dp1, vector<int> &p, int cur, int par) {
    p[cur] = par;
    dp1[cur][0] = 1;
    for (auto nxt: edges[cur]) {
        if (nxt == par) continue;
        dfs1(edges, dp1, p, nxt, cur);
        for (int64_t i = 1; i < n; ++i) {
            dp1[cur][i] += dp1[nxt][i-1];
        }
    }
}

void dfs2(const vector<vector<int>> &edges, const vector<vector<int64_t>> &dp1, vector<vector<int64_t>> &dp2, int cur, int par) {
    if (par != -1) {
        dp2[cur][0] = 1;
        for (int64_t i = 1; i < n; ++i) {
            dp2[cur][i] += dp2[par][i-1];
        }
    }
    for (int64_t i = 2; i < n; ++i) {
        int64_t total = 0;
        /*for (auto nxt: edges[cur]) {
            if (nxt == par) continue;
            total += dp1[nxt][i];
        }*/
        total = dp1[cur][i-1];
        if (i < n - 1) {
            for (auto nxt: edges[cur]) {
                if (nxt == par) continue;
                dp2[nxt][i] += total - dp1[nxt][i-2];
            }
        }
    }
    for (auto nxt: edges[cur]) {
        if (nxt == par) continue;
        dfs2(edges, dp1, dp2, nxt, cur);
    }
}

int main() {
    cin >> n;

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

    vector<vector<int64_t>> dp1(n, vector<int64_t>(n));
    vector<vector<int64_t>> dp2(n, vector<int64_t>(n));
    dp2[0][0] = 1;
    vector<int> par(n);
    dfs1(edges, dp1, par, 0, -1);
    dfs2(edges, dp1, dp2, 0, -1);

    /*for (int i = 0; i < n; ++i) {
        cout << i << ": ";
        for (int d = 0; d < n; ++d) {
            cout << dp1[i][d] << ' ';
        }
        cout << '\n';

    }

    for (int i = 0; i < n; ++i) {
        cout << i << ": ";
        for (int d = 0; d < n; ++d) {
            cout << dp2[i][d] << ' ';
        }
        cout << '\n';
    }*/

    for (int d = 1; d < n; ++d) {
        if (d % 2 != 0) {
            cout << "0 ";
            continue;
        } 
        int64_t triples = 0;
        for (int i = 0; i < n; ++i) {
            vector<int64_t> bar1(edges[i].size());
            vector<int64_t> bar2(edges[i].size());
            vector<int64_t> bar3(edges[i].size());
            bar3[0] = 0;
            bar2[0] = 0;
            if (edges[i][0] == par[i]) {
                bar1[0] = dp2[i][d/2];
            } else {
                bar1[0] = dp1[edges[i][0]][d/2-1];
            }
            for (int j = 1; j < (int)edges[i].size(); ++j) {
                if (edges[i][j] == par[i]) {
                    bar3[j] = bar3[j-1] + bar2[j-1]*dp2[i][d/2];
                    bar2[j] = bar2[j-1] + bar1[j-1]*dp2[i][d/2];
                    bar1[j] = bar1[j-1] + dp2[i][d/2];
                } else {
                    bar3[j] = bar3[j-1] + bar2[j-1]*dp1[edges[i][j]][d/2-1];
                    bar2[j] = bar2[j-1] + bar1[j-1]*dp1[edges[i][j]][d/2-1];
                    bar1[j] = bar1[j-1] + dp1[edges[i][j]][d/2-1];
                }
            }
            triples += bar3[edges[i].size()-1];
        }
        cout << triples << ' ';
    }
    cout << '\n';
    
    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: ACCEPTED

Test 33

Verdict: ACCEPTED

Test 34

Verdict: ACCEPTED

Test 35

Verdict: ACCEPTED

Test 36

Verdict: ACCEPTED

Test 37

Verdict: ACCEPTED

Test 38

Verdict: ACCEPTED

Test 39

Verdict: ACCEPTED

Test 40

Verdict: ACCEPTED