洛谷P3647 [APIO2014] 连珠线 题解

题目链接：P3647 [APIO2014] 连珠线

题意：

在达芬奇时代，有一个流行的儿童游戏称为连珠线。当然，这个游戏是关于珠子和线的。线是红色或蓝色的，珠子被编号为 \(1\) 到 \(n\)。这个游戏从一个珠子开始，每次会用如下方式添加一个新的珠子：

Append(w, v)：一个新的珠子 \(w\) 和一个已经添加的珠子 \(v\) 用红线连接起来。

Insert(w, u, v)：一个新的珠子 \(w\) 插入到用红线连起来的两个珠子 \(u, v\) 之间。具体过程是删去 \(u, v\) 之间红线，分别用蓝线连接 \(u, w\) 和 \(w, v\)。

每条线都有一个长度。游戏结束后，你的最终得分为蓝线长度之和。

给你连珠线游戏结束后的游戏局面，只告诉了你珠子和链的连接方式以及每条线的长度，没有告诉你每条线分别是什么颜色。

你需要写一个程序来找出最大可能得分。即，在所有以给出的最终局面结束的连珠线游戏中找出那个得分最大的，然后输出最大可能得分。

\(1 \leq n \leq 200000\)。

开学前两天准备狂刷题，结果在这题上卡了一下午（😭

本文主要参考了link，所以主要是自己的总结型题解（q779太菜了

容易发现这是一道树形dp

首先可以想到一个瞎七搭八的dp，也就是设结点 \(u\) 和父亲的连边涂什么颜色

但是这个dp不好判断合法性，这篇博客讲的比较详细，不过这个也比较容易发现

于是考虑避免那种“/\形”的蓝色边，只考虑“\类型”的，也就是fa[u]-u-son[u]的

可以发现此时如果固定了一个结点做根，就可以避免“/\形”的蓝色边出现

同时也方便dp了（并且有一种经典换根dp的感觉了，虽然我当时看不出）

设 \(f[u][0/1]\) 表示 \(u\) 所在子树中，\(u\) 作为或不作为蓝线的中点是能得到的最大价值

前者比较简单，不是蓝线中点，则可以连蓝线中点，也可以连红线。 \[ f[u][0]=\sum_{v \in \text{son}[u]} \max(f[v][0],f[v][1]+w(u,v)) \tag{1} \] 后者较为麻烦，首先它和前者唯一的区别在于，它必须有一个儿子作为这条蓝线的终点。显然这个儿子是某个 \(f[v][0]\) 。因此我们可以把 \(f[u][0]\) 的直接初始化到 \(f[u][1]\) 上，然后去掉这个 \(v\) 的贡献，并加上它的新贡献。 \[ f[u][1]=f[u][0]+\max_{v \in \text{son}[u]}(f[v][0]+w(u,v)-\max(f[v][0],f[v][1]+w(u,v))) \tag{2} \] 有点长，不过后面那个max就是 \(f[u][0]\) 里面的那个max

然后我们就有了一个固定根情况下的dp，时间复杂度 \(O(n^2)\) ，还过不了

然后这里就要换根dp发挥作用了。

我们考虑一个点 \(u\) 的儿子变成了 \(u\) 的父亲会有什么影响

首先这个儿子对 \(u\) 的贡献没了，并且有可能转移方程中的最大值也没了。

（于是我们记录一个次大值，貌似是经典套路）

然后 \(u\) 会变成新的儿子给原来的儿子（现在的父亲）贡献

方便起见，我们在第一遍dp的时候用vector记录一个 \(g[u][0/1][j]\)

表示对于 \(u\) ，不考虑第 \(j\) 个儿子的贡献时能获得的最大价值

\(g[u][0][j]\) 直接减去 \(j\) 的贡献就好了，

对于 \(g[u][1][j]\) ，如果 \(j\) 恰好是最大值，那就加上次大值，否则不变

这里的最大值、次大值就是指 \((2)\) 里的 \[ \max\limits_{v \in \text{son}[u]}(f[v][0]+w(u,v)-\max(f[v][0],f[v][1]+w(u,v))) \] 换根的过程中，枚举 \(u\) 的儿子作为整棵树的根。值得注意的是，换根以后 \(u\) 的父亲就会变成 \(u\) 的儿子。因此我们要先重新算出 \(u\) 的父亲对 \(u\) 的贡献，然后再换根

时间复杂度 \(O(n)\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(2e5+15)

struct Edge
{
    int u,v,w,next;
}e[N<<1];
int pos=1,head[N];
int n,ans,fa[N],len[N],f[N][2];
vector<int> son[N],g[N][2],mx[N]; // mx[u][i] 表示u所在子树不考虑i时的max
void addEdge(int u,int v,int w)
{
    e[++pos]={u,v,w,head[u]};
    head[u]=pos;
}
void dfs1(int u,int Fa)
{
    f[u][0]=0;f[u][1]=-INF;
    int mx1=-INF,mx2=-INF;
    for(int i=head[u]; i; i=e[i].next)
    {
        int v=e[i].v,w=e[i].w;
        if(v==Fa)continue;
        len[v]=w;fa[v]=u;
        son[u].push_back(v);
        dfs1(v,u);
        f[u][0]+=max(f[v][0],f[v][1]+w);
        int t=f[v][0]+w-max(f[v][0],f[v][1]+w);
        if(t>mx1)swap(mx1,mx2),mx1=t;
        else if(t>mx2)mx2=t; // 次大值
    }
    f[u][1]=f[u][0]+mx1;
    for(int i=head[u]; i; i=e[i].next)
    {
        int v=e[i].v,w=e[i].w;
        if(v==Fa)continue;
        g[u][0].push_back(f[u][0]-max(f[v][0],f[v][1]+w));
        if(f[v][0]+w-max(f[v][0],f[v][1]+w)==mx1)
        {
            g[u][1].push_back(g[u][0].back()+mx2);
            mx[u].push_back(mx2);
        }else
        {
            g[u][1].push_back(g[u][0].back()+mx1);
            mx[u].push_back(mx1);
        }
    }
}
void dfs2(int u)
{
    for(int i=0; i<son[u].size(); i++)
    {
        f[u][0]=g[u][0][i],f[u][1]=g[u][1][i];
        if(fa[u])
        {
            f[u][0]+=max(f[fa[u]][0],f[fa[u]][1]+len[u]); // 注意这里的f已经不是dfs1的f了
            f[u][1]=f[u][0]+max(mx[u][i],f[fa[u]][0]+len[u]-max(f[fa[u]][0],f[fa[u]][1]+len[u]));
        }
        ans=max(ans,f[son[u][i]][0]+max(f[u][0],f[u][1]+len[son[u][i]]));
        dfs2(son[u][i]);
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1,u,v,w; i<n; i++)
    {
        cin >> u >> v >> w;
        addEdge(u,v,w);addEdge(v,u,w);
    }
    dfs1(1,1);dfs2(1);
    cout << ans << '\n';
    return 0;
}