AC. 梦想

frank_c1

[BZOJ 3302] 树的双中心

发布于2016年01月08日 | 暂无评论 | 1,553阅读 | 图论,

题目描述

2016010801

输入格式

第一行为N,1<N<=50000,表示树的节点数目,树的节点从1到N编号。

接下来N-1行,每行两个整数U,V,表示U与V之间有一条边。

再接下N行,每行一个正整数,其中第i行的正整数表示编号为i的节点权值为W(i)。

输入数据保证节点1到任意节点距离不超过100。

输出格式

将最小的S(x,y)输出,结果保证不超过10^9。

题目解析

观察发现,这道题有一个很明显的O(n ^ 2)暴力,即枚举每一条边,计算切掉这条边后形成的两棵树各自的重心。求一次重心O(n),树形DP即可。

然后注意到这棵树的高度很小,我们试着从这一点上优化。考虑DP转移的方式,我们发现只要不断向权值和较大的子树走即可获得最优解。因为我们每一步的转移是O(1)的,所以O(h)的时间即可找到重心。这样我们只要记录每个节点子树权值和最大的儿子即可,但是有一个问题,如果此时这个儿子经过了被切掉的边,是不能走的,所以还要记录子树权值和次大的儿子。

先预处理一些信息。还是枚举切掉每一条边,然后分别找两棵树的重心,根据预处理的信息,在转移时顺便计算代价,单次复杂度O(h)。总时间复杂度O(nh)

注意本题有些坑点,如果不够仔细可能掉进去,本人在一个小错误上WA了近20次(血泪史)。另外本题特别给力,3302 = 2447 = 2103,三倍经验哦~~