AC. 梦想

frank_c1

[APIO 2014] Beads and wires

发布于2017年04月16日 | 暂无评论 | 625阅读 | 动态规划

题意简述

n个点。现在你可以选择一个点x开始,执行若干操作。

1. 选择一个未被加入的点x和一个已经加入的点y,在x,y之间连一条红边。

2. 选择一个未被加入的点x和两个连有红边的点y, z,删去y, z之间的红边,并在x, yx, z之间分别连一条蓝边。

现在给你一棵带边权的树,作为操作完毕后的图,唯一没有标明的是边的颜色。

你需要给每条边染上颜色,满足是一种合法的方案。最大化蓝边的总长度。

1 \le n \le 200000

算法讨论

为方便描述,我们称长度为k的链为k元链。

我们观察到操作2才能形成蓝色边。而每次操作2形成的具体形态是什么呢?二元链。

进一步分析题目性质,如果我们确定了一个点作为根,那么实质上我们在进行两种操作。一是选定一个点集中的点在其下面挂一个二元链,对答案产生贡献。二是选定一个点集中的点在其下面挂一个一元链,对答案不产生贡献。

这样就可以DP了。不妨先枚举根c。对于点x,设f_{x,0}x子树不向上继续延伸的答案,f_{x,1}x子树还需要向上延伸一条边的答案。则答案是f_{c,0}。转移比较简单,仔细考虑一下就好。

但由于枚举根,复杂度是O(n ^ 2)的。分析一下DP的过程,我们发现可以快速地从某个点的信息中挖去一个子树或加上一个子树。也就是说如果我们知道x作为根的答案,维护一些信息后可以快速知道所有x相邻的点作为根的答案。这样的话我们先对点1作一个DP再DFS一遍计算出其他点的答案即可。

时间复杂度O(n)。我的实现不太优美,是O(n \log n)的TAT