[Luogu]P6748 『MdOI R3』Fallen Lord
本文最后更新于 168 天前,其中的信息可能已经有所发展或是发生改变。

Before the Beginning

转载请将本段放在文章开头显眼处,如有二次创作请标明。

原文链接:https://www.codein.icu/lp6748/

题意

给出一棵树,决定边权,使得每个点相连的边最少有 $\lfloor \dfrac{num}{2} \rfloor + 1$ 条权值 $\leq a_i$,最大化所有边权和。

解法

考虑动态规划,对以每个点为根的子树进行考虑。
定义合法边为权值 $\leq a_i$ 的边。
子树内分两种状态:

  1. 至少 $\lfloor \dfrac{num}{2} \rfloor$ 条合法边与根相连,根与其父亲连合法边后该点满足条件。
  2. 至少 $\lfloor \dfrac{num}{2} \rfloor + 1$ 条合法边与根相连,根与其父亲任意连边该点都满足条件。

定义第一种状态下,子树中最大边权和为 $f(x)$,第二种状态下为 $g(x)$,考虑进行转移。

两点之间的边,只有三种情况:

  1. $w = a_u$
  2. $w = a_v$
  3. $w = m$

第一种为 $u$ 提供一条合法边,第二种为 $v$ 提供一种合法边,第三种不提供合法边。
此时需要对 $a_u$ 与 $a_v$ 的大小进行讨论。

当 $a_u > a_v$ 时:

  1. $w = a_u$,为 $u$ 提供合法边,不为 $v$ 提供合法边,该儿子贡献为 $g(v) + a_u$,且贡献合法边。
  2. $w = a_v$,为 $v$ 提供合法边,同时为 $u$ 提供合法边,该儿子贡献为 $\max{f(v),g(v)} + a_v$,且贡献合法边。
  3. $w = m$,不提供合法边,该儿子贡献为 $g(v) + m$,不贡献合法边。

同理,当 $a_u < a_v$ 时:

  1. $w = a_u$,为 $u$ 提供合法边,同时为 $v$ 提供合法边,该儿子贡献为 $\max{f(v),g(v)} + a_u$,且贡献合法边。
  2. $w = a_v$,为 $v$ 提供合法边,不为 $u$ 提供合法边,该儿子贡献为 $\max{f(v),g(v)} + a_v$,不贡献合法边。
  3. $w = m$,不提供合法边,该儿子贡献为 $g(v) + m$,不贡献合法边。

等于的情况就不赘述了。
特殊地,叶子节点 $f(x) = 0,g(x) = -INF$,必须依赖父亲来满足合法边需求。

每一个儿子,三种情况合并后都有两个状态:贡献合法边、不贡献合法边。
将贡献合法边时的最大贡献记为 $d(x,0)$,不贡献合法边时的最大贡献记为 $d(x,1)$。
现在考虑选出至少 $\lfloor \dfrac{num}{2} \rfloor$ 个贡献合法边的儿子时的权值和如何计算。
将儿子们以 $d(x,0) – d(x,1)$ 降序排序,取前 $\lfloor \dfrac{num}{2} \rfloor$ 个贡献合法边,往后取较大的即可。

考虑选出 $> \lfloor \dfrac{num}{2} \rfloor$ 个贡献合法边的儿子时的权值和如何计算。
同样将儿子们以 $d(x,0) – d(x,1)$ 降序排序,强制取前 $\lfloor \dfrac{num}{2} \rfloor + 1$ 个 $d(x,0)$,往后取较大的即可。

时间复杂度为 $O(n \log n)$,可以通过。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
#define DEBUG
using namespace std;
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 1e6 + 100;
const int maxm = 2 * maxn;
const long long INF = 1ll<<60;
struct node
{
    int to, next;
}E[maxm];
int head[maxn];
inline void add(const int &x, const int &y)
{
    static int tot = 0;
    E[++tot].next = head[x], E[tot].to = y, head[x] = tot;
}
int n, m, a[maxn], out[maxn];
long long f[maxn], g[maxn];
struct status
{
    long long d1, d2;
}s[maxn];
inline bool cmp(const status &a, const status &b)
{
    return a.d1 - a.d2 > b.d1 - b.d2;
}
void dfs(int u, int fa)
{
    vector<int> sons;
    for (int p = head[u]; p; p = E[p].next)
    {
        int v = E[p].to;
        if (v == fa) continue;
        dfs(v, u), sons.push_back(v);
    }
    if (sons.empty()) return (void)(g[u] = -INF);
    int num = sons.size();
    for (int i = 1;i <= num;++i)
    {
        int v = sons[i-1];
        if (a[u] >= a[v])
        {
            s[i].d1 = max(g[v] + a[u], max(f[v], g[v]) + a[v]);
            s[i].d2 = g[v] + m;
            if(a[u] == m) s[i].d2 = 0;
        }
        else
        {
            s[i].d1 = max(f[v], g[v]) + a[u];
            s[i].d2 = max(g[v] + m, f[v] + a[v]);
        }
    }
    sort(s + 1, s + 1 + num, cmp);
    int mid = out[u] / 2;
    for (int i = 1; i <= mid;++i) f[u] += s[i].d1;
    for (int i = mid + 1;i <= num;++i) f[u] += max(s[i].d1,s[i].d2);
    if (mid + 1 > num)
    {
        g[u] = -INF;
        return;
    }
    g[u] = f[u] + s[mid + 1].d1 - max(s[mid + 1].d1,s[mid + 1].d2);
//    for (int i = 1;i <= mid + 1;++i) g[u] += s[i].d1;
//    for (int i = mid + 2;i <= num;++i) g[u] += max(s[i].d1, s[i].d2);
}
int main()
{
    read(n), read(m);
    for (int i = 1; i <= n; ++i) read(a[i]);
    for (int i = 1;i<n;++i)
    {
        int a, b;
        read(a), read(b), add(a, b), add(b, a), out[a]++, out[b]++;
    }
    int root = 1;
    for(int i = 2;i <= n;++i) if(out[i] == 1) {root = i;break;}
    dfs(root, 0);
    if (g[root] < 0) puts("-1");
    else printf("%lld\n", g[root]);
    return 0;
}
本文标题:[Luogu]P6748 『MdOI R3』Fallen Lord
本文作者:Clouder
本文链接: https://www.codein.icu/lp6748/
转载请标明。

评论

  1. 6月前
    2020-8-12 14:48:00

    太强了,接触了算法之后愈加觉得强

发送评论 编辑评论

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