APIO2014 连珠线 ( beads)

本文主要是介绍APIO2014 连珠线 ( beads)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

有$n$个珠子，一开始只有一个珠子，随后的$n-1$个珠子以如下方式之一加入：
1.直接向已有的珠子连一条红线；
2.在已有连红线的两个珠子之间的红线拆段，再分别向它们连一条线。
给出最后形成的树（不给出边的颜色），且每条边有权值，求蓝边权值和的最大值。

题解

原始想法：根据样例猜一下，是不是每个点都可连两条蓝边，保证蓝边不相交，树形DP一下即可？显然是错的（APIO题目哪有这么简单）。考虑什么情况不合法，通过乱画发现对于有主动连蓝边的两个点之间不能是非祖先后代关系，但这个条件也不好限制呀，然后越想越乱。
正解：其实刚才完全在为自己找麻烦了，这种时候一定是没有利用好题目的某些性质。再回到题面，考虑建树的过程，以一开始的节点为根（既然是树，依题意确定一个根肯定更好做），建红边就直接加儿子，建蓝边就把一对父子之间加入一个点，所以刚才乱七八糟的限制就变得清晰了：即蓝边只能连接型如fa-u-son，所以确定一个根后，树形DP即可。但我们不知道根是哪个，考虑O(1)换根，发现每次换只会影响到u和v的DP值，所以可以直接选1为根，再依次换根即可。
总结：本题的突破口在于以题目中那个第一个点为根（如果能从题目出发去想，其实不难想到），在这之后的想法都十分清晰自然，不要总是大概理解题意之后就不加分析随便乱想，再加上本来就差的思考力，必然gg。（感觉这样下去APIO要暴零了啊）

这篇关于APIO2014 连珠线 ( beads)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---