2020-2021:teams:farmer_john:2sozx:codeforces_round_646_div._2
差别
这里会显示出您选择的修订版和当前版本之间的差别。
|
2020-2021:teams:farmer_john:2sozx:codeforces_round_646_div._2 [2020/06/01 11:52] 2sozx 创建 |
2020-2021:teams:farmer_john:2sozx:codeforces_round_646_div._2 [2020/06/01 11:52] (当前版本) 2sozx [E] |
||
|---|---|---|---|
| 行 13: | 行 13: | ||
| * zyf的做法tql!!! | * zyf的做法tql!!! | ||
| =====E===== | =====E===== | ||
| - | * 题意：给一棵以 $1$ 为根的树，大小为 $n(n\le2\times10^5)$,每个节点有一个值 $0/1$ 和一个目标值 $0/1$ 和一个代价 $a_i$,选取一个节点可以交换其子树内节点的值，代价为选取的节点个数 $k\timesa_i$,问让每个节点的值和目标值相等的最小代价，如果不可能输出 $-1$。 | + | * 题意：给一棵以 $1$ 为根的树，大小为 $n(n\le2\times10^5)$,每个节点有一个值 $0/1$ 和一个目标值 $0/1$ 和一个代价 $a_i$,选取一个节点可以交换其子树内节点的值，代价为选取的节点个数 $k\times a_i$,问让每个节点的值和目标值相等的最小代价，如果不可能输出 $-1$。 |
| * 题解：对于两个节点如果要交换一定是在两个节点的 $lca$ 到 $1$ 的路径中代价最小的点交换，因此 $dfs$ 时记录此节点到 $1$ 的代价最小值即可，且在子树中可以先行交换，依旧是正确的，所以在 $dfs$ 回溯的时候算一下答案即可。 | * 题解：对于两个节点如果要交换一定是在两个节点的 $lca$ 到 $1$ 的路径中代价最小的点交换，因此 $dfs$ 时记录此节点到 $1$ 的代价最小值即可，且在子树中可以先行交换，依旧是正确的，所以在 $dfs$ 回溯的时候算一下答案即可。 | ||
| =====F===== | =====F===== | ||
| * 题意：摸摸摸 | * 题意：摸摸摸 | ||
| * 题解： | * 题解： | ||
2020-2021/teams/farmer_john/2sozx/codeforces_round_646_div._2.1590983552.txt.gz · 最后更改: 2020/06/01 11:52 由 2sozx
