Before the Beginning

转载请将本段放在文章开头显眼处，如有二次创作请标明。
原文链接：https://www.codein.icu/lp3174/

题意

题目传送门

定义毛毛虫：
在树上选一条链，链上每个点所连接的点都被包括在毛毛虫上。

定义毛毛虫的大小：
毛毛虫包含的节点数。

求一棵树上最大的毛毛虫的大小。

解法

使用动态规划的方法。

定义状态

类比树上最长链的求法。
定义 $f[i]$ 为以 $i$ 为一个端点、在以 $i$ 为根的子树中最大的毛毛虫包含的节点数量。

上图中，标红节点为 $f_5$ 所覆盖的节点，加粗边为毛毛虫的链。

状态转移

考虑如何进行转移。
儿子数不同时分类讨论。

无儿子

单个点的情况， $f_i = 1$。

单儿子

只有一个儿子的情况。

将父亲节点接上作为新的端点。

$f_i = f_{son} + 1$

多儿子

选择 $f_{son}$ 最大的儿子接上。
其他儿子也被挂在毛毛虫上，加上儿子数，减去在 $f_{son}$ 中被计入的儿子。

$f_i = f_{son} + num + 1 – 1$
即 $f_i = f_{son} + num$

统计答案

确定状态后，用状态统计出答案。
依然分类讨论。

无儿子

没有儿子，单点情况。

如果当前点有父亲：

$ans = f_u + 1$

如果当前点无父亲：

$ans = f_u$

可以处理单个根节点的情况。

单儿子

如果当前点有父亲，父亲会挂在毛毛虫上。

$ans = f_u + 1$

如果当前点无父亲：

$ans = f_u$

多儿子

类比求树上最长链可知，最长毛毛虫可能在两个儿子中取得。

记录 $f$ 最大和第二大的儿子，记为 $a,b$。

如果当前点有父亲：

$ans = f_a + f_b + num – 2 + 1 + 1$，减去被重复计算的两个儿子，加上当前点和父亲点。
即 $ans = f_a + f_b + num$。

如果当前点无父亲：

$ans = f_a + f_b + num – 1$

代码

按照文章中的分类方法写的，可能略显繁琐。

#include <cstdio>
using namespace std;
template <typename T>
inline T _max(const T &a, const T &b) { return a > b ? a : b; }
template <typename T>
inline void read(T &r)
{
    static char c;
    r = 0;
    for (c = getchar(); c > '9' || c < '0'; c = getchar());
    for (; c >= '0' && c <= '9'; r = (r << 1) + (r << 3) + (c ^ 48), c = getchar());
}
const int maxn = 3e5 + 100;
struct node
{
    int to, next;
} E[maxn << 1];
int head[maxn];
inline void add(const int &x, const int &y)
{
    static int tot;
    E[++tot].next = head[x];
    E[tot].to = y;
    head[x] = tot;
}
int n, m, ans;
int f[maxn];
void dfs(int u, int from)
{
    int num = 0, maxx = 0, secx = 0;
    int v;
    for (int p = head[u]; p; p = E[p].next)
    {
        v = E[p].to;
        if (v == from)
            continue;
        dfs(v, u);
        ++num;
        if (f[v] > maxx)
            secx = maxx, maxx = f[v];
        else if (f[v] > secx)
            secx = f[v];
    }
    if (num == 0)
    {
        f[u] = 1;
        if (from == 0)
            ans = _max(ans, f[u]);
        else
            ans = _max(ans, f[u] + 1);
        return;
    }
    if (num == 1)
    {
        f[u] = maxx + 1;
        if (from == 0)
            ans = _max(ans, f[u]);
        else
            ans = _max(ans, f[u] + 1);
        return;
    }
    //multison
    f[u] = maxx + num;
    if (from == 0)
        ans = _max(ans, maxx + secx + num - 1);
    else
        ans = _max(ans, maxx + secx + num);
}
int main()
{
    read(n);
    read(m);
    int a, b;
    for (int i = 1; i <= m; ++i)
    {
        read(a);
        read(b);
        add(a, b);
        add(b, a);
    }
    dfs(1, 0);
    printf("%d", ans);
    return 0;
}