P3647 [APIO2014]连珠线 树形DP+换根法

\(dp\)果然太菜了

思路

最先添加了一个点\(u\)

然后

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

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

只有这两种操作

所以对于最后得到的树上蓝线的部分只能是父亲\(->\)当前点\(->son\)

这样的话就方便定义状态了

我们用\(f[x][1]\)表示\(x\)为当前点时它所在的子树最长蓝线

类似地,我们用\(f[x][0]\)表示\(x\)为父亲 或 \(son\)或根本不连蓝线时(既它不是当前点)它所在的子树最长蓝线

\[f[x][0]=\displaystyle\sum_{v\in{son[x]}}max(f[v][0],f[v][1]+w_{x->v})\]

\(f[x][1]\)稍微有点麻烦

\[f[x][1]=f[x][0]-max(f[v][1]+w_{x->v},f[v][0])+f[v][0]+w_{x->v}\]

理解:由于\(x\)为当前点 所以它至多可以与一个儿子连蓝边(当然选最大的啊)

这里的最大的不是指\(w_{x->v}\)最大 而是指与哪一个儿子连边的值最大(\(f[x][1]\)最大)

然后考虑换根

换根

换跟时有一个跟着第一次操作的处理

inline void dfs(int x,int fa)
{
    f[x][0] = 0,f[x][1] = -inf;
    int max1,max2;
    max1 = max2 = -inf;
    for(reg i = head[x];i;i = edge[i].next)
    {
        int v = edge[i].v,w = edge[i].w;
        if(v == fa) continue;
        father[v] = x,len[v] = w;
        son[x].push_back(v);
        dfs(v,x);
        f[x][0] += max(f[v][0],f[v][1] + w);
        int pre = -max(f[v][0],f[v][1] + w) + f[v][0] + w;
        if(pre > max1) max2 = max1,max1 = pre;
        else if(pre > max2) max2 = pre;//记录最大值以及次大值 
    }
    f[x][1] = f[x][0] + max1;
    //这以上是以1为根的
    //  f[x][1] = f[x][0] - max(f[v][0],f[v][1] + w) + f[v][0] + w;
    //这里是上面说的处理
    for(reg i = head[x];i;i = edge[i].next)
    {
        int v = edge[i].v,w = edge[i].w;
        if(v == fa) continue;
        dp[x][0].push_back(f[x][0] - max(f[v][0],f[v][1] + w));
        //以下dp[x][0/1][i]都是忽略了它的father的 
        //dp[x][0][i]表示以edge[i].v为根时 以x为根所在子树(不包含它以前的father那部分) 的f[x][0] 
        int pre = -max(f[v][0],f[v][1] + w) + f[v][0] + w;
        if(max1 == pre) maxx[x].push_back(max2),dp[x][1].push_back(max2 + dp[x][0].back());
        else maxx[x].push_back(max1),dp[x][1].push_back(max1 + dp[x][0].back());
        //同理这里是 dp[x][1][i]表示以edge[i].v为根时 以x为根所在子树(同上) 的f[x][1] 
        //这里 最大值次大值的使用就很明显了 
        //maxx的作用dfs2(换根)时会用到 (再讲) 
    }
}

然后 换根时

仔细看看代码 注意 父亲 当前点 当前根 当前点的儿子 应该就可以理解了

(我当时理解了好久)

inline void dfs2(int x)
{
    for(reg i = 0;i < son[x].size();i++)
    {
        //换根 
        f[x][1] = dp[x][1][i],f[x][0] = dp[x][0][i]; //dp记录的状态 
        if(father[x])
        {
            //dfs时我们没有考虑father 所以这里得再算一下它的贡献
            int v = father[x];
            f[x][0] += max(f[v][0],f[v][1] + len[x]);
            f[x][1] = f[x][0] + max(maxx[x][i],f[v][0] + len[x] - max(f[v][0],f[v][1] + len[x])); //加最大的 
        } 
        ans = max(ans,f[son[x][i]][0] + max(f[x][0],f[x][1] + len[son[x][i]]));
        dfs2(son[x][i]);
    }
}

\(Eventually,Code\)

#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define reg register int
#define isdigit(x) ('0' <= x&&x <= '9')
template<typename T>
inline T Read(T Type)
{
    T x = 0,f = 1;
    char a = getchar();
    while(!isdigit(a)) {if(a == '-') f = -1;a = getchar();}
    while(isdigit(a)) {x = (x << 1) + (x << 3) + (a ^ '0');a = getchar();}
    return x * f;
}
const int MAXN = 200010,inf = 0x3f3f3f3f;
int ans,cnt,head[MAXN],father[MAXN],len[MAXN],f[MAXN][2];
vector<int> son[MAXN],maxx[MAXN],dp[MAXN][2];
struct node{int v,w,next;}edge[MAXN << 1];
inline void addedge(int u,int v,int w)
{
    edge[++cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt;
}
inline void dfs(int x,int fa)
{
    f[x][0] = 0,f[x][1] = -inf;
    int max1,max2;
    max1 = max2 = -inf;
    for(reg i = head[x];i;i = edge[i].next)
    {
        int v = edge[i].v,w = edge[i].w;
        if(v == fa) continue;
        father[v] = x,len[v] = w;
        son[x].push_back(v);
        dfs(v,x);
        f[x][0] += max(f[v][0],f[v][1] + w);
        int pre = -max(f[v][0],f[v][1] + w) + f[v][0] + w;
        if(pre > max1) max2 = max1,max1 = pre;
        else if(pre > max2) max2 = pre;//记录最大值以及次大值 
    }
    f[x][1] = f[x][0] + max1;
    //这以上是以1为根的
    //  f[x][1] = f[x][0] - max(f[v][0],f[v][1] + w) + f[v][0] + w;
    //这里是上面说的处理
    for(reg i = head[x];i;i = edge[i].next)
    {
        int v = edge[i].v,w = edge[i].w;
        if(v == fa) continue;
        dp[x][0].push_back(f[x][0] - max(f[v][0],f[v][1] + w));
        //以下dp[x][0/1][i]都是忽略了它的father的 
        //dp[x][0][i]表示以edge[i].v为根时 以x为根所在子树(不包含它以前的father那部分) 的f[x][0] 
        int pre = -max(f[v][0],f[v][1] + w) + f[v][0] + w;
        if(max1 == pre) maxx[x].push_back(max2),dp[x][1].push_back(max2 + dp[x][0].back());
        else maxx[x].push_back(max1),dp[x][1].push_back(max1 + dp[x][0].back());
        //同理这里是 dp[x][1][i]表示以edge[i].v为根时 以x为根所在子树(同上) 的f[x][1] 
        //这里 最大值次大值的使用就很明显了 
        //maxx的作用dfs2(换根)时会用到 (再讲) 
    }
}
inline void dfs2(int x)
{
    for(reg i = 0;i < son[x].size();i++)
    {
        //换根 
        f[x][1] = dp[x][1][i],f[x][0] = dp[x][0][i]; //dp记录的状态 
        if(father[x])
        {
            //dfs时我们没有考虑father 所以这里得再算一下它的贡献
            int v = father[x];
            f[x][0] += max(f[v][0],f[v][1] + len[x]);
            f[x][1] = f[x][0] + max(maxx[x][i],f[v][0] + len[x] - max(f[v][0],f[v][1] + len[x])); //加最大的 
        } 
        ans = max(ans,f[son[x][i]][0] + max(f[x][0],f[x][1] + len[son[x][i]]));
        dfs2(son[x][i]);
    }
}
int main()
{
    int n = Read(1);
    for(reg i = 1;i < n;i++)
    {
        int u = Read(1),v = Read(1),w = Read(1);
        addedge(u,v,w),addedge(v,u,w);
    }
    dfs(1,0);
    dfs2(1);
    printf("%d",ans);
    return 0;
}

P3647 [APIO2014]连珠线 树形DP+换根法

上一篇:windows CMakeLists.txt


下一篇:ElasticSearch3:RestAPI