标签: 换根DP

2 篇文章

义乌中学暑假集训 2021.07.15 C
白云有一颗 $n$ 个节点的树,每个点有一个点权 白兔需要找到两条点不相交的路径,要求最大化这两条路径覆盖点的点权和 $n\leq 10^5$。 Sol 换根 DP。 考虑两条路径的形态。 从两个子树中各抽出一条链。在一棵子树中抽一条经过根的链,再在剩余的儿子的子树中抽一条链。在一棵子树中抽一条子树内的链,再在经过这个子树的父亲抽一条链。 然后维护…
义乌中学暑假集训 2021.07.13 C
给定一棵 $n$ 个节点的带权有根树,保证每个节点权值均为非负整数。 定义 $f(x)$​,表示对于节点 $x$​,包含 $x$​ 的节点的平均值最大的连通块内平均值。 求 $\min_{i=1}^n f(i)$。 $n\leq 10^5$。 Sol 既有最小也有最大,想到二分。 可以二分答案,每次 check 的时候数字权值减去 mid,跑一次换…