Luogu3174 [HAOI2009]毛毛虫（树形DP）题解

题意

中文题面，不再赘述

算法

树形DP + 贪心乱搞

思路

所有无法描述的正解都是贪心算法

不过这道题还是可以感性理解的

设(f_u)为以(u)为根的子树内最大毛毛虫的大小（尽管答案并不可以由它直接得出），则：

[f_u = max(f_v) + 1 + min(siz_u - 1, 0) quad [vin child_u] ]

其中，(siz_u)为(u)的儿子数量。

这里有个小(trick)，用(min(siz_u-1,0))可以方便地处理叶子节点，而中间的(1)为(u)本身。

显然答案并不是任何一个(f)，按照树的直径的思路，最大值应该是由连在一个点上的最大与次大的(f)加上它其他连向的节点（包括父亲），我们只需要在(DFS)的时候处理一下就可以了：

[Ans = max(Ans, Max + Second + 1 + (fa_u eq root) + max(0, siz_u - 2)) ]

其中，(Max)，(Second)分别表示所有儿子中(f)的最大/次大值。

参考代码

#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn = 3e5 + 10;
int n,head[maxn << 1],num,ans,m;
struct Edge{
    int then,to;
}e[maxn << 1];

void add(int u, int v){e[++num] = (Edge){head[u], v}; head[u] = num;}

int f[maxn];
void DFS(int u, int fa){
    int Max = 0, Sec = 0, siz = 0;
    for(int i = head[u]; i; i = e[i].then){
        int v = e[i].to;
        if(v == fa) continue;
        DFS(v, u); siz ++; 
        if(f[v] >= Max) Sec = Max, Max = f[v];
        else if(f[v] > Sec) Sec = f[v];
    }
    ans = max(ans, Max + Sec + 1 + (fa != u) + max(0, siz - 2));
    f[u] = Max + 1 + max(0, siz - 1); 
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; ++ i){
        int u,v; scanf("%d%d", &u, &v);
        add(u, v); add(v, u);
    } DFS(1, 1);
    printf("%d
", ans);
    return 0;
}

细节题，差评