[Baltic2003]Gem

[Baltic2003]Gem

Time Limit:2000MS Memory Limit:65536K
Total Submit:18 Accepted:11
Case Time Limit:1000MS

Description

给出一棵树,要求你为树上的结点标上权值,权值可以是任意的正整数
唯一的限制条件是相临的两个结点不能标上相同的权值,要求一种方案,使得整棵树的总价值最小。

Input

先给出一个数字N,代表树上有N个点,N<=10000
下面N-1行,代表两个点相连

Output

最小的总权值

Sample Input

Sample Output

Source
这题首先是不能用奇偶层染色的办法来做的,我构造出了至少需要1-3的反例,同时用数学归纳法可以证明对于任意n,都有树不能用1-n达到最优解(提示:使用大量叶子节点逼迫某节点染2。。)。。
但是我的构造法弄出来的反例的大小至少是指数增长的,所以我感觉对于N<=10000,10种颜色足够了。。更精确的测试表明3种就OK了(!!!!!我可以构造出1000个以内的需要4种颜色的反例啊囧。。这个数据好弱啊。。)。。然后就是简单的树形DP。。。比赛的时候很明显直接DP就可以了。。证明不重要(*^__^*) 嘻嘻……

14

10 7 5 1 2 1 7 8 9 4 1 9 7 5 6 10 2 9 3
囧。。由于不会绘图软件。。自己手绘了一个反例。。
可以看出在一些情况中奇偶层的叶子都很多。。如果奇偶染色肯定要悲剧。。
可以用类似的方法构造出需要1-4、1-5、1-6的反例。。

7 thoughts on “[Baltic2003]Gem

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>