Loading... [题目链接](https://www.luogu.org/problem/P2279) <!--more--> --- - 设计状态：$f[x][0-4]$表示以x为根节点的子树，能覆盖到向上2到-2个节点需要的最小消防局数量，这样明显$f[x][0]\leq f[x][1]\leq f[x][2] \leq f[x][3] \leq f[x][4]$所以转移的时候尽量选第二维大的转移，能保证最小： - $f[x][0] = \sum f[y][4]+1$ - 如果能延伸到x的祖父节点，那么x必须为消防局，所以答案是x的所有儿子向下2个，及x所有孙子的儿子都能被覆盖即可，因为x为消防局，所以数量加一。 $$ f[x][1] = min\{\sum_{s\in t且s \not= k} f[s][3]+f[k][0]\} $$ - 延伸到x的父亲，只需要保证所有的孙子已经被覆盖，并且其中一个儿子可以向上延伸2个，这就意味着所有的x的儿子和x本身还有x的父亲都可以被这个消防局覆盖。 - $f[x][2]$同理 - $f[x][3] = \sum f[y][2]$ - 能保证x的儿子们都被覆盖，相当于儿子们自己都被覆盖。 - $f[x][4] = \sum f[y][3]$ - 同理 ```cpp #include<bits/stdc++.h> using namespace std; int n; struct Edge{ int to, nxt; }e[2009]; int head[1009], tot; int f[1009][5]; void add(int x, int y){ e[++tot].to = y; e[tot].nxt = head[x]; head[x] = tot; } void dfs(int x, int fa){ for(int i = head[x]; i; i = e[i].nxt){ int y = e[i].to; if(y == fa) continue; dfs(y, x); f[x][0] += f[y][4]; f[x][3] += f[y][2]; f[x][4] += f[y][3]; } f[x][0] += 1; f[x][1] = f[x][2] = 0x3f3f3f3f; for(int i = head[x]; i; i = e[i].nxt){ int y = e[i].to; if(y == fa) continue; f[x][1] = min(f[x][1], f[x][4] - f[y][3] + f[y][0]); f[x][2] = min(f[x][2], f[x][3] - f[y][2] + f[y][1]); } f[x][1] = min(f[x][1], f[x][0]); f[x][2] = min(f[x][2], f[x][1]); f[x][3] = min(f[x][3], f[x][2]); f[x][4] = min(f[x][4], f[x][3]); } int main(){ scanf("%d", &n); for(int i = 2; i <= n; i++){ int y; scanf("%d", &y); add(i, y), add(y, i); } dfs(1, 0); printf("%d\n", f[1][2]); return 0; } ``` Last modification：March 14, 2020 © Allow specification reprint Like 如果觉得我的文章对你有用，请随意赞赏