[Luogu]P3174 [HAOI2009]毛毛虫
本文最后更新于 280 天前,其中的信息可能已经有所发展或是发生改变。

Before the Beginning

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

题意

题目传送门

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

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

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

解法

使用动态规划的方法。

定义状态

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

ExampleFor_F5

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

状态转移

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

无儿子

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

单儿子

只有一个儿子的情况。

SingleSon

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

$f_i = f_{son} + 1$

多儿子

MultiSon

选择 $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$

多儿子

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

MultiSonAns

记录 $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;
}
本文标题:[Luogu]P3174 [HAOI2009]毛毛虫
本文作者:Clouder
本文链接: https://www.codein.icu/lp3174/
转载请标明。
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇