• [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));$

    相关文章
    相关标签/搜索
    4887铁筼结果开奖结果小说 稷山县| 凤城市| 玉林市| 尖扎县| 克东县| 乳源| 从化市| 外汇| 沁阳市| 读书| 太仆寺旗| 青河县| 漠河县| 剑河县| 杨浦区| 温州市| 南阳市| 卫辉市| 泌阳县| 临汾市| 探索| 湖南省| 新绛县| 塔河县| 永昌县| 武乡县| 山阳县| 南通市| 洪雅县| 宣武区| 三江| 吴堡县| 梅州市| 辰溪县| 普格县| 广宁县| 彭泽县| http://fa.hz0j0r4vo.fun http://fa.hz0j2r9vo.fun http://fa.hz0j0r8vo.fun http://fa.hz0j1r2vo.fun http://fa.hz0j0r0vo.fun