2020-2021:teams:farmer_john:jjleo:wqs二分
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:jjleo:wqs二分 [2020/06/06 21:27] jjleo [林克卡特树] |
2020-2021:teams:farmer_john:jjleo:wqs二分 [2020/06/25 23:07] (当前版本) jjleo ↷ 链接因页面移动而自动修正 |
||
|---|---|---|---|
| 行 13: | 行 13: | ||
| =====林克卡特树===== | =====林克卡特树===== | ||
| * 题意:给出一颗$n$个节点的树，每条边有边权，从中挑选$k+1$个互不相交的链，使得所有被选中的边的权值和最大。 | * 题意:给出一颗$n$个节点的树，每条边有边权，从中挑选$k+1$个互不相交的链，使得所有被选中的边的权值和最大。 | ||
| - | * 题解: | + | * 题解:设$f(x)$为选择$x$个互不相交的链的边权最大值，这个函数也是上凸的，太菜了不会证。然后就可以wqs二分转化为树形dp，每条链附加一个$-mid$的权值即可。这个树形dp的过程非常巧妙，通过微调枚举顺序减少了代码的复杂度。设$f[x][i]$表示只考虑点$x$所在的子树，且点$x$的度为$i$时的最大权值，因为只能出现链所以$0 \le i \le 2$，子树中代码如下，注意枚举顺序不能改，因为前两个转移都用到了上次的结果。<code cpp>void dfs(int i, int fa){ |
| + | f[i][0] = Data(0, 0), f[i][1] = f[i][2] = Data(-mid, 1); | ||
| + | for(int j = 0;j < v[i].size();j++){ | ||
| + | int x = v[i][j].first, y = v[i][j].second; | ||
| + | if(x == fa) continue; | ||
| + | dfs(x, i); | ||
| + | Data g = max(f[x][0], max(f[x][1], f[x][2])); | ||
| + | f[i][2] = max(f[i][1] + f[x][1] + Data(y + mid, -1), f[i][2] + g); | ||
| + | f[i][1] = max(f[i][0] + f[x][1] + Data(y, 0), f[i][1] + g); | ||
| + | f[i][0] = max(f[i][0], f[i][0] + g); | ||
| + | } | ||
| + | }</code> | ||
| =====Tree I===== | =====Tree I===== | ||
| 行 21: | 行 32: | ||
| =====CF1279F===== | =====CF1279F===== | ||
| - | * [[Educational Codeforces Round 79 (Rated for Div. 2) Virtual participation|F题]] | + | * [[educational_codeforces_round_79_rated_for_div._2_virtual_participation|F题]] |
2020-2021/teams/farmer_john/jjleo/wqs二分.1591450054.txt.gz · 最后更改: 2020/06/06 21:27 由 jjleo
