杂题

题意

给定一棵(2n-1)个点的树,(n)个白点,((n-1))个黑点。
对于每个黑点,两个儿子节点,分别为黑点和白点,边分为红、蓝两种颜色,黑点到儿子节点一条为红,一条为蓝。
白点均为叶子节点。
需要标记(n-1)条边,对于每个白点,令至根的路径上还有(x)条红边没标记,(y)条蓝边没标记,每个白点有三个关键字((a_i,b_i,c_i)),其贡献为(c_i imes(b_i+x) imes(a_i+y))
求最小贡献。
(nle 20000),树深度不超过(40)

做法

强制标记(n-1)条边,另显然函数导数是单调不降的
就带权二分
发现对于同色选择的边,是连续的一段

(f_{i,a,b})为到(i)点时,(i)至根红边状态为(a),蓝边状态为(b)
(a=0),则表示(i)至根红边全部选;否则表示至根红边个数为(a-1),子树内均不选红边。蓝边同理。
(a,b)均不为(0),子树状态是确定的,可以预处理出来。故(f_{i,a,b})的状态数为(O(ndep)),转移是(O(1))的。
然后预处理子树总贡献复杂度为(O(ndep^2))

总复杂度(O(ndeplogV+ndep^2))

原文地址:https://www.cnblogs.com/Grice/p/12960607.html