题解 P4516 【[JSOI2018]潜入行动】

· · 题解

简单的树形dp。

设f[i][j][0/1][0/1]表示i的子树中已安装j个装置，i是/否安装，是/否被控制的方案数，dp方程随便推推注意下细节就行。

复杂度O(nk)

然后观察数据，n远大于k，如果树太深答案一定是0，出题人可能不想让输出0的人拿高分，那么这颗树节点的度数大概率非常大，近似一个菊花图。

这时再写链表显然是不明智的做法，利用vector内存连续的特性，一般情况下比链表要快了。就不会出现提交记录里面的一片80分，开O2后100分的尴尬情况。

现在各大比赛纷纷支持C++11，还开O2，以后存图是不是都不用写链表了（雾

虽然这里面没有这篇题解但我还是要放出来！

void dfs(int u, int fa) {
    siz[u] = 1;
    f[u][0][0][0] = f[u][1][1][0] = 1;
    for (auto v : E[u])
        if (v != fa) {
            dfs(v, u);
            for (int i = 0, lim = min(siz[u], k); i <= lim; i++) {
                g[i][0][0] = f[u][i][0][0], f[u][i][0][0] = 0;
                g[i][0][1] = f[u][i][0][1], f[u][i][0][1] = 0;
                g[i][1][0] = f[u][i][1][0], f[u][i][1][0] = 0;
                g[i][1][1] = f[u][i][1][1], f[u][i][1][1] = 0;
            }
            //这样大概，可能，也许比两个循环要快那么一点点吧。
            for (int i = 0, lim = min(siz[u], k); i <= lim; i++)
                for (int j = 0, lim2 = min(siz[v], k); j <= lim2 && i + j <= k; j++) {
                    add(f[u][i + j][0][0], g[i][0][0] * f[v][j][0][1]);
                    add(f[u][i + j][0][1], g[i][0][1] * (f[v][j][0][1] + f[v][j][1][1]) + g[i][0][0] * f[v][j][1][1]);
                    add(f[u][i + j][1][0], g[i][1][0] * (f[v][j][0][0] + f[v][j][0][1]));
                    add(f[u][i + j][1][1], g[i][1][0] * (f[v][j][1][0] + f[v][j][1][1]) + g[i][1][1] * ((ll)f[v][j][0][0] + f[v][j][0][1] + f[v][j][1][0] + f[v][j][1][1]));
                }
            siz[u] += siz[v];
        }
}