AIM Tech Round 3 (Div. 1) C. Centroids(树形dp)

题意: $给定N\le 4\times 10^5的一棵树,询问每个点是否能通过删掉1条边再添加1条边成为重心$$重心:删除这个点,所有连通分量的最大大小\le n/2$     Read more
TaoSama's avatar
TaoSama Aug 26, 2016

Codeforces 85C Petya and Tree(树形dp)

题意: $N\le 10^5的一棵满二叉搜索树,点权1\le A_i\le 10^9$$满二叉搜索树:每个节点的儿子个数为0或者2$$给定Q\le 10^5询问,每次查询一个值1\le q\le 10^9,保证值没有在BST中出现过$$并且查询过程中一定会出错有且仅有一次,即本该去左子树去了右子树,反之亦然$$求在BST中查询这个值的期望$     Read more
TaoSama's avatar
TaoSama Aug 01, 2016

2016 计蒜之道 微软的员工福利 (简单、中等)(dp)

题意: $给定一颗N个节点的树,根为1,每个点可以在2种物品价值中2选1$$每个节点会减少一定的价值f_i,其中x_i为所有直接儿子选择物品的极差(最大值-最小值)$$$f_i=\lceil{x_i\over 1000}\rceil\times 666\times i $$$求所有员工最大满意度的和$     Read more
TaoSama's avatar
TaoSama Jun 12, 2016