CW 模拟赛 T2.迁跃

Yorg / 2024-10-29 / 原文

题面

似乎有原题, 但是很偏
挂个 pdf
题面下载

算法

一眼树形 dp
~~然而考场上没想出来~~
很显然有一个式子
令 $f_u$ 表示从 $u$ 进入子树, 再通过迁越回到点 $u$ 的最大价值
则有

\[f_u = \sum_{exist\text{ }u \rightarrow v}^{(v, w)} \max (f_v + w - k, 0) \]

但是我们并不一定要回到根(考场上想不出来的原因), 于是枚举最后停止的点 $t$
于是答案的式子为

\[\max\left\{f_t + \sum^{(u, v, w)\text{ }on\text{ }the\text{ }list\text{ }from\text{ }1\text{ }to\text{ }t}_{u \rightarrow v} \big [ f_u - \max{\left(f_v + w - k, 0 \right) + w \big] }\right\} \]

意思就是统计不在这条链上的子树的贡献和链的总边权

代码

dfs 回溯时转移即可

#include <bits/stdc++.h>
#define int long long
const int MAXN = 1e5 + 20; //641

int n, k;

struct node
{
    int to, w;
    int next;
} Edge[MAXN << 1];
int cnt = 0;
int head[MAXN];
void init() { for (int i = 1; i <= n; i++) { head[i] = -1; } }

void addedge(int u, int v, int w)
{
    Edge[++cnt].to = v;
    Edge[cnt].w = w;
    Edge[cnt].next = head[u];
    head[u] = cnt;
}

int dp[MAXN];
int Ans[MAXN];
void dfs1(int Now, int fa)
{
    for (int i = head[Now]; ~i; i = Edge[i].next)
    {
        int NowTo = Edge[i].to, NowW = Edge[i].w;

        if(NowTo == fa) continue;

        dfs1(NowTo, Now);
        dp[Now] += std::max(dp[NowTo] + NowW - k, 0ll);
    }
}

void dfs2(int Now, int fa, int Now_Con)
{
    Ans[Now] = std::max(Ans[Now], dp[Now] + Now_Con);
    for (int i = head[Now]; ~i; i = Edge[i].next)
    {
        int NowTo = Edge[i].to, NowW = Edge[i].w;

        if (NowTo == fa)
            continue;

        dfs2(NowTo, Now, Now_Con + dp[Now] - std::max(dp[NowTo] + NowW - k, 0ll) + NowW);
    }
}

int solve()
{
    dfs1(1, -1);
    dfs2(1, -1, 0);

    int Answer = 0;
    for (int i = 1; i <= n; i++)
    {
        Answer = std::max(Answer, Ans[i]);
    }

    return Answer;
}

signed main()
{
    scanf("%lld %lld", &n, &k);
    init();
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v, w;
        scanf("%lld %lld %lld", &u, &v, &w);

        addedge(u, v, w);
        addedge(v, u, w);
    }

    printf("%lld", solve());

    return 0;
}

/*
4 4
1 2 114514
1 3 2
3 4 1

114514
*/

/*
4 4
1 2 114514
1 3 2
3 4 3

114515
*/