洛谷3647：连珠线

洛谷3647：连珠线

题意描述：

• 有\(n\)个珠子，编号为\(1\)到\(n\)。从一个珠子开始，每次都会用如下的方式来添加一个新的珠子：
  • \(append(w,v):\)一个新的珠子\(w\)和一个已经添加的珠子用红线连接起来。
  • \(insert(w,u,v):\)一个新的珠子\(w\)插入到已经用红线连起来的两个珠子\(u,v\)之间。具体过程是删去\(u,v\)之间的红线，分别用蓝线连接\(u,w\)和\(w,v\)。
• 每条线都有一个长度。游戏结束后，最终得分为蓝线长度之和。
• 给你连珠线游戏结束后的局面，只告诉你珠子和链的连接方式以及每条线的长度，没告诉你每条线分别是什么颜色。
• 找出最大得分。

思路：

• 通过思考（模拟样例）可以发现，蓝线一定是\(son(x)-x-fa(x)\)这样的存在形式。
• 那么先随便固定一个根进行\(dp\)。
• 设\(f(x,0/1)\)表示以\(x\)为根的子树汇总，不选/选\(x\)作为蓝线的中点所能得到的最大价值。
• 有状态转移方程：
  • 当\(x\)不是中点的时候，对于\(x\)的一个儿子\(y\)，他们之间的连线有两种可能，红线或者是蓝线。如果是蓝线，那么有\(f(y,1)+w(x,y)\)；如果是红线，那么有\(f(y,0)\)。于是状态转移方程为\(f(x,0)+=max_{y\in son(x)}(f(y,0),f(y,1)+w(x,y))\)。
  • 如果\(x\)是中点，那么显然会连下去一条蓝线。
  • 假设选定了\(y\)为连接蓝线的儿子，那么对于其他儿子，他们和\(f(x,0)\)的转移是一样的。
  • 那么有\(f(x,1)=f(x,0)\)。
  • 只有点\(y\)从\(max\{f(y,1)+w,f(y,0)\}\)变成了\(f(y,0)+w\)。
  • 所以就取连蓝线的最大值，也就是\(max_{y\in son(x)}\{f(y,0)+w(x,y)-max\{f(y,0),f(y,1)+w(y,x)\}\}\).
  • 所以有转移方程\(f(x,1)=f(x,0)+max_{y\in son(x)}\{f(y,0)+w(x,y)-max\{f(y,0),f(y,1)+w(y,x)\}\}\).
• 当然这是在固定了根的情况下进行的，根的不同会导致答案的不同，所以接下来考虑换根。
• 设\(g(x,y,0/1)\)表示当前\(x\)不考虑\(y\)这个儿子和\(x\)作不作为蓝线中点的最大值。
• 那么显然有\(g(x,y,0)=f(x,0)-max(f(y,0),f(y,1)+w(x,y))\)。
• \(g(x,y,1)\)比较麻烦。
• 现在考虑某个结点的儿子节点变为父亲节点了会怎么样？
• 首先这个子节点的贡献没了，所以max值可能会改变，所以需要记录一个\(f[y][0] + z - max(f[y][0], f[y][1]+z)\)的次大值（当前儿子是最大值的点就换成次大值），同时原来的父亲变为了现在的儿子产生了贡献。所以应当重新计算\(fa(x)\)对\(x\)的贡献，然后进行换根。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
const int INF = 0x3f3f3f3f;

int head[maxn], nex[maxn<<1], edge[maxn<<1], ver[maxn<<1], tot;
inline void add_edge(int x, int y, int z){
    ver[++tot] = y; edge[tot] = z;
    nex[tot] = head[x]; head[x] = tot;
}

int n;
int fa[maxn], len[maxn], ans = -INF;
int f[maxn][3];
vector<int> son[maxn], dp[maxn][2], maxx[maxn];

void dfs(int x, int ff)
{
    f[x][0] = 0;
    f[x][1] = -INF;
    int mx1, mx2; mx1 = mx2 = -INF; //记录最大值与次大值
    for(int i = head[x]; i; i = nex[i])
    {
        int y = ver[i], z = edge[i];
        if(y == ff) continue;
        fa[y] = x; len[y] = z;
        son[x].push_back(y);
        dfs(y, x);
        f[x][0] += max(f[y][0], f[y][1] + z);
        int pre = f[y][0] + z - max(f[y][0], f[y][1]+z);
        if(pre > mx1) mx2 = mx1, mx1 = pre;
        else if(pre > mx2) mx2 = pre;
    }
    f[x][1] = f[x][0] + mx1;

    for(int i = head[x]; i; i = nex[i])
    {
        int y = ver[i], z = edge[i];
        if(y == ff) continue;
        dp[x][0].push_back(f[x][0]-max(f[y][0], f[y][1]+z));
        int pre = f[y][0] + z - max(f[y][0], f[y][1]+z);
        if(mx1 == pre) maxx[x].push_back(mx2), dp[x][1].push_back(mx2 + dp[x][0].back());
        else maxx[x].push_back(mx1), dp[x][1].push_back(mx1 + dp[x][0].back());
    }
}

void solve(int x)
{
    for(int i = 0; i < (int)son[x].size(); i++)
    {
        //换根
        f[x][1] = dp[x][1][i], f[x][0] = dp[x][0][i];
        if(fa[x]) 
        {
            int y = fa[x];
            f[x][0] += max(f[y][0], f[y][1]+len[x]); //加上父亲的贡献
            f[x][1] = f[x][0] + max(maxx[x][i], f[y][0]+len[x]-max(f[y][0], f[y][1]+len[x]));
        }
        ans = max(ans, f[son[x][i]][0] + max(f[x][0], f[x][1]+len[son[x][i]]));
        solve(son[x][i]);
    }
}

int main()
{
    scanf("%d", &n);
    for(int i = 1, x, y, z; i++ <= n - 1;)
    {
        scanf("%d%d%d", &x, &y, &z);
        add_edge(x, y, z); add_edge(y, x, z);
    }
    dfs(1, 0); solve(1);
    cout << ans << endl;
    return 0;
}

洛谷3647：连珠线

原文：https://www.cnblogs.com/zxytxdy/p/12189051.html