• [APIO2014]连珠线

    3647 [APIO2014]连珠线

    题目描述

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

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

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

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

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

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

    输入格式

    第一行一个正整数 $n$,表示珠子的数量。珠子从 1 到 n 编号。

    接下来 n - 1 行每行三个整数 $a_{i},b_{i},c_{i}$?。保证 $1 \leqslant a_{i},b_{i} \leqslant n$,$1 \leqslant c_{i} \leqslant 10000$。表示 ai? 号珠子和 bi? 号珠子间连了长度为 ci? 的线。

    输出格式

    输出一个整数,表示最大可能得分。

    输入输出样例

    输入 #1
    5
    1 2 10
    1 3 40
    1 4 15
    1 5 20
    输出 #1
    60
    输入 #2
    10
    4 10 2
    1 2 21
    1 3 13
    6 7 1
    7 9 5
    2 4 3
    2 5 8
    1 6 55
    6 8 34
    输出 #2
    140

    说明/提示

    【样例描述1】

    可以通过如下方式获得 60 分:首先从 3 号珠子开始。

    5 和 3 连起来。(线长度任意)

    在 3 和 5 之间插入 $11$。(线长分别为 40 和 20)。

    把 2 和 1 用长度为 $10$ 的线连起来。

    把 4 和 1 用长度为 $15$ 的线连起来。

    【限制与约定】

    第一个子任务共 13 分,满足 $1\leqslant n \leqslant 10$

    第二个子任务共 15 分,满足 $1\leqslant n \leqslant 200$

    第三个子任务共 29 分,满足 $1\leqslant n \leqslant 10000$

    第四个子任务共 43 分,满足 $1\leqslant n \leqslant 200000$

     

    Solution:

    为了方便,我们把每个珠子看成一个节点

    我们非常开心的发现,结果肯定是一棵边颜色不同的树

    由于刚开始只有任意的一个节点,就相当于我们选择一个节点为根,

    然后进行两种操作:

    1.每次扩展一个节点的儿子,即把一个节点和已经在树上的一个点连上一条红边,且不在这两个点之间加珠子:

    分享图片

    或者扩展一个节点的孙子再扩展这个孙子的爸爸,就是把树上的一个节点连到另一个节点上,在把一个节点插到这两个节点之间,把两条边染成蓝色,即:

    分享图片

    分享图片

     好的,假设以1号点为根,我们可以列出一个DP方程式

    f[i][0/1]表示当前节点是否为中点获得的最大价值

    $f[i][0]=\sum\limits_{j}^{j \in son[i]}max(f[j][0],f[j][1]+dis(i,j));$

    相关文章
    相关标签/搜索
    蓝月亮精选料免费大全930 迁安市| 宜春市| 凤台县| 黄梅县| 平安县| 珲春市| 广灵县| 高碑店市| 天全县| 襄城县| 太康县| 连云港市| 承德市| 得荣县| 北辰区| 湖口县| 尼木县| 安平县| 吴江市| 旌德县| 新余市| 高邮市| 公主岭市| 庆元县| 池州市| 新竹市| 灵宝市| 乌拉特前旗| 延庆县| 黄梅县| 格尔木市| 北宁市| 湘潭市| 永德县| 固安县| 崇阳县| 象州县| http://fa.hz0j2r4vo.fun http://fa.hz0j1r5vo.fun http://fa.hz0j1r3vo.fun http://fa.hz0j1r0vo.fun http://fa.hz0j2r5vo.fun