某島

… : "…アッカリ~ン . .. . " .. .
March 10, 2020

HDU 4625. JZPTREE

https://www.cnblogs.com/TinyWong/p/10436473.html
HDU 4507
https://en.wikipedia.org/wiki/Stirling_number

經典樹上 DP + 斯特林數分拆冪運算,斯特林數需要學習一下《具體數學》。


//}/* .................................................................................................................................. */

const int N = int(5e4) + 9, K = int(5e2) + 9;

VI adj[N];
int n, k;

Int S[N][K], f[N][K], g[N][K];

#define v (*it)
void dfs1(int u = 1, int p = 0) {
    f[u][0] = 1; REP_1(i, k) f[u][i] = 0;
    ECH(it, adj[u]) if (v != p) {
        dfs1(v, u);
        REP(i, k+1) f[u][i] += f[v][i]+i*f[v][i-1];
    }
}

void dfs2(int u = 1, int p = 0){
    ECH(it, adj[u]) if (v != p) {
        g[v][0] = g[u][0];
        REP_1(i, k) {
            Int g1 = g[u][i]-(f[v][i]+i*f[v][i-1]);
            Int g2 = g[u][i-1]-f[v][i-1]-(i-1)*(i-2 >= 0 ? f[v][i-2] : Int(0));
            g[v][i] = f[v][i]+g1+i*g2;
        }
        dfs2(v, u);
    }
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    S[0][0] = 1; FOR(i, 1, K) REP_1(j, i) S[i][j] = S[i-1][j-1]+S[i-1][j]*j;

    Rush {
        RD(n, k); REP_1(i, n) adj[i].clear();
        DO(n-1) {
            int x, y; RD(x, y);
            adj[x].PB(y);
            adj[y].PB(x);
        }

        dfs1(); REP(i, k+1) g[1][i] = f[1][i]; dfs2();

        REP_1(u, n) {
            Int z = 0; REP(i, k+1) z += S[k][i] * g[u][i];
            cout << z << endl;
        }
    }
}