【Luogu P3174 】[HAOI2009]毛毛虫

GJY-JURUO 2019-12-07 原文

前言：

虽然很多人和我想法一样 ~~，但我还是不要脸地写了这题解~~

题目：

链接

大意：

在一棵树上取一条最长链以及它所连接的结点总共的结点个数

思路:

取链：

用树形\(DP\)就可以轻而易举的解决这个问题：

\(f_x\)表示以\(x\)为根节点的树的深度

转移方程：

\[f_x=max\{f_y + 1 \} (y\in son(x))\]

那么以\(x\)为根节点的树的最长链就是\(f_x\)加上次大的子树深度，下方代码区以\(ans\)来表示。

代码：

void dp(int x, int root)
{
    f[x] = 1;
    int maxn = 0, lown = 0; //最大 与 次大
    for (int i = head[x]; i; i = next[i])
    {
        int y = to[i];
        if (y == root) continue;
        dp(y, x);
        if(f[y] > lown)
        {
            if(f[y] > maxn) lown = maxn, maxn = f[y];
            else lown = f[y];
        }
        f[x] = max(f[x], f[y] + 1);
    }
    ans = max(ans, f[x] + lown);
}

链所连接的结点：

也就是说只用加上周边的结点就可以了，不用再递归下去。

那我们先在\(\texttt{main()}\)里记录每个节点的儿子个数

然后递归就可以直接加上去就可以惹！

代码：

void dp(int x, int root)
{
    f[x] = 1;
    int num = 0;
    int maxn = 0, lown = 0;
    for (int i = head[x]; i; i = next[i])
    {
        int y = to[i];
        if (y == root) continue;
        dp(y, x);
        if(f[y] > lown)
        {
            if(f[y] > maxn) lown = maxn, maxn = f[y];
            else lown = f[y];
        }
        f[x] = max(f[x], f[y] + son[x] - 1);  //减1是因为父结点也算进去了
    }
    ans = max(ans, lown + maxn + son[x] - 1);
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        ADD(x, y);
        ADD(y, x);
        son[x] ++, son[y] ++;
    }
    dp(1, 0);
    printf("%d", ans);
    return 0;
}

祝\(CSP.rp++\)