【bzoj3677】[Apio2014]连珠线

2015.05.06 10:11 Wed | 37次阅读 | 旧日oi | 固定链接 | 源码

Description

在列奥纳多·达·芬奇时期,有一个流行的童年游戏,叫做“连珠线”。不出所料,玩这个游戏只需要珠子和线,珠子从1到礼编号,线分为红色和蓝色。游戏
开始时,只有1个珠子,而接下来新的珠子只能通过线由以下两种方式被加入:
1.Append(w,杪):-个新的珠子w和一个已有的珠子杪连接,连接使用红线。
2.Insert(w,u,v):-个新的珠子w加入到一对通过红线连接的珠子(u,杪)
之间,并将红线改成蓝线。也就是将原来u连到1的红线变为u连到w的蓝线与W连到V的蓝线。
无论红线还是蓝线,每条线都有一个长度。而在游戏的最后,将得到游戏的
最后得分:所有蓝线的长度总和。
现在有一个这个游戏的最终结构:你将获取到所有珠子之间的连接情况和所
有连线的长度,但是你并不知道每条线的颜色是什么。
你现在需要找到这个结构下的最大得分,也就是说:你需要给每条线一个颜
色f红色或蓝色),使得这种连线的配色方案是可以通过上述提到的两种连线方式
操作得到的,并且游戏得分最大。在本题中你只需要输出最大的得分即可。

Input

第一行是一个正整数n,表示珠子的个数,珠子编号为1刭n。
接下来n-l行,每行三个正整数ai,bi(l≤ai10000),表示有一条长度为ci的线连接了珠子ai和珠子bi。

Output

输出一个整数,为游戏的最大得分。

Sample Input

5
1 2
1 3 4 0
1 4 1 5
1 5 2 0

Sample Output

60

HINT

数据范围满足1≤n≤200000。

题解

树形dp的模型还是很容易看出来的。就是转移实在是恶心到爆啊
我在代码里写题解吧

我的程序

#include<vector>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
using namespace std;
#define inf 0x3f3f3f3f
#define maxn 500010
struct edge{
    int to,next,val;
}e[maxn<<1];
int h[maxn],tp;
void ae(int u,int v,int w)
{
    e[++tp].to=v;e[tp].next=h[u];
    e[tp].val=w;h[u]=tp;
}
int n,len[maxn],f[maxn][2],cnt,ans,fa[maxn],cost[maxn];
vector <int> son[maxn],dp[maxn][2],best[maxn];
void update(int &a,int b)
{
    if(b<0) return;
    if (b>a) a=b;
}
void dfs(int u)
{
    f[u][1]=-inf;f[u][0]=0;//f[u][0]:表示u不是作为两条蓝线的中间点时子树形成的最大值 
                            //f[u][1]:表示u作为两条蓝线的中间点时子树形成的最大值 
    int mx1=-inf,mx2=-inf;//最大值和次大值 
    for (int v,i=h[u];e[i].to;i=e[i].next)
    {
        v=e[i].to;
        if(v==fa[u]) continue;
        cost[v]=e[i].val; fa[v]=u; dfs(v);
        f[u][0]+=max(f[v][0],f[v][1]+e[i].val);//f[u][0]的转移比较简单
        //下面4行,-max里的东西,相当于是从f[u][0]里减掉v的贡献,后面的东西,是强制v不作为中间节点,u作为中间节点的贡献 
        if(-max(f[v][0],f[v][1]+e[i].val)+f[v][0]+e[i].val>mx1)
            mx2=mx1,mx1=-max(f[v][0],f[v][1]+e[i].val)+f[v][0]+e[i].val;
        else if(-max(f[v][0],f[v][1]+e[i].val)+f[v][0]+e[i].val>mx2)
            mx2=-max(f[v][0],f[v][1]+e[i].val)+f[v][0]+e[i].val;
    }
    f[u][1]=f[u][0]+mx1;
    for (int v,i=h[u],tmp,key;e[i].to;i=e[i].next)
    {
        v=e[i].to;
        if(v==fa[u]) continue;
        son[u].push_back(v);
        dp[u][0].push_back(tmp=f[u][0]-max(f[v][0],f[v][1]+e[i].val));//在不考虑v这个儿子时f[u][0]的值 
        if(-max(f[v][0],f[v][1]+e[i].val)+f[v][0]+e[i].val==mx1) key=mx2; 
        else key=mx1;
        dp[u][1].push_back(tmp+key); //在不考虑v这个儿子时f[u][1]的值 ,mx1,mx2就是在这里用到的。 
        best[u].push_back(key);
    }
}
void work(int u,int id)
{
   f[u][0]=dp[u][0][id];//不包含id儿子时的f[u][0] 
    f[u][1]=dp[u][1][id];//不包含id儿子时的f[u][1] 
    if(fa[u])//把u的父亲看做u的儿子节点并更新f[u]
    {
        f[u][0]+=max(f[fa[u]][0],f[fa[u]][1]+cost[u]);
        f[u][1]=f[u][0]+max(best[u][id],-max(f[fa[u]][0],f[fa[u]][1]+cost[u])
            +f[fa[u]][0]+cost[u]);
    }
    //把u看做son[u][id]的儿子节点,更新答案。 
    ans=max(ans,f[son[u][id]][0]+max(f[u][0],f[u][1]+cost[son[u][id]]));
}
void tree_dp(int u)
{
    for(int s=son[u].size(),i=0;i<s;i++)
    work(u,i),tree_dp(son[u][i]);
}
int main()
{
    scanf("%d",&n);
    for(int u,v,w,i=1;i<n;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        ae(u,v,w);ae(v,u,w);
    }
    dfs(1); //强制1为根,先做一遍。 
    ans=max(ans,f[1][0]);
    tree_dp(1);//因为可能有以其它点为根的情况,但是需要修改的值很少,可以O(n)处理。 
    printf("%d",ans);
    return 0;
}```