Luogu

UOJ

分析

首先考虑连线的过程。可以发现,以最先加的点为根,所有的蓝线都会是儿子-自己-父亲的形式。

于是我们枚举根,然后 f。设 $f_{u,0/1}$ 表示以 $u$ 为根的子树,$u$ 是或不是蓝线中点的最大得分。

首先考虑 $f_{u,0}$ 的转移。此时每个子节点要么不是中点,要么是中点。于是有

$$ f_{u,0}=\sum_{v\in son_u}\max\left\{f_{v,0},f_{v,1}+w_{u,v}\right\} $$

再考虑 $f_{u,1}$ 的转移。此时我们钦定一个子节点作为与 $u$ 蓝线相连的点。于是有

$$ f_{u,1}=f_{u,0}+\max_{v\in son_u}\left\{-\max\left\{f_{v,0},f_{v,1}+w_{u,v}\right\}+f_{v,0}+w_{u,v}\right\} $$

这样子是 $O(n^2)$ 的,结合随机算法可能可以拿 57 分。

因为我们要求每个节点作为根时的 $f$ 值,因此可以考虑换根 DP。这里介绍一种从题解里看来的方法。

我们考虑 $u$ 的一个子节点 $v$ 变为根时,$f_{u,0/1}$ 都应将 $v$ 的贡献去掉。$f_{u,0}$ 可以直接减去 $v$ 的贡献,而 $f_{u,1}$ 需要维护一个次大值来去除 $v$ 的贡献。

然后去除贡献之后直接把 $u$ 的 $f$ 值算到 $v$ 里去,就可以得到以 $v$ 为根时的 f 值了。

具体的,在代码实现中维护一个 $dp_{u,0/1,v}$ 表示去掉子节点 $v$ 后 $f_{u,0/1}$ 的值,同时维护一下去掉子节点 $v$ 后子树中 $-\max\left\{f_{v,0},f_{v,1}+w_{u,v}\right\}+f_{v,0}+w_{u,v}$ 的最大值。然后换根时把 $f_{u,0/1}$ 设为 $dp_{u,0/1,v}$ ,然后把 $u$ 的贡献加到 $v$ 中去,再更新一下答案并递归处理即可。

感觉不是很讲得清啊...不过应该看看代码就能看懂了。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;
const int inf=0x3f3f3f3f;

int n;

struct edge { int v,w,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v,int w) {
    static int cnt=0;
    e[++cnt]=(edge){v,w,head[u]},head[u]=cnt;
}

int ans;
int f[N][2],fw[N];
vector<int> ch[N],dp[N][2],mx[N];
inline void dfs(int u,int fa) {
    f[u][0]=0,f[u][1]=-inf; int mx1=-inf,mx2=-inf;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v,w=e[i].w; if (v==fa) continue;
        fw[v]=w,dfs(v,u);
        f[u][0]+=max(f[v][0],f[v][1]+w);
        int tmp=-max(f[v][0],f[v][1]+w)+f[v][0]+w;
        if (tmp>mx1) mx2=mx1,mx1=tmp;
        else if (tmp>mx2) mx2=tmp;
    }
    f[u][1]=f[u][0]+mx1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v,w=e[i].w; if (v==fa) continue;
        ch[u].push_back(v);
        dp[u][0].push_back(f[u][0]-max(f[v][0],f[v][1]+w));
        int tmp=-max(f[v][0],f[v][1]+w)+f[v][0]+w;
        if (tmp==mx1) {
            dp[u][1].push_back(dp[u][0].back()+mx2);
            mx[u].push_back(mx2);
        } else {
            dp[u][1].push_back(dp[u][0].back()+mx1);
            mx[u].push_back(mx1);
        }
    }
}
inline void redfs(int u,int fa) {
    for (re int i=0;i<ch[u].size();++i) {
        f[u][0]=dp[u][0][i],f[u][1]=dp[u][1][i];
        if (fa) {
            f[u][0]+=max(f[fa][0],f[fa][1]+fw[u]);
            int tmp=-max(f[fa][0],f[fa][1]+fw[u])+f[fa][0]+fw[u];
            f[u][1]=f[u][0]+max(mx[u][i],tmp);
        }
        ans=max(ans,f[ch[u][i]][0]+max(f[u][0],f[u][1]+fw[ch[u][i]]));
        redfs(ch[u][i],u);
    }
}

int main() {
    n=read();
    for (re int i=1;i<n;++i) {
        int u=read(),v=read(),w=read();
        addEdge(u,v,w),addEdge(v,u,w);
    }
    dfs(1,0),ans=f[1][0],redfs(1,0);
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 10 月 21 日 10 : 34 PM