用户工具

站点工具


2020-2021:teams:farmer_john:2sozx:codeforces_round_660_div._2

这是本文档旧的修订版!


目录

C

  • 题意:给定一颗树,每个节点有一个值 $p$ 代表这个节点最终有多少人。起始所有人从根节点 $1$ 出发向自己的目标沿着最短路径前进,每个人有两种情绪,只有好情绪能变成坏情绪。在每个节点定义一个函数 $h$ 为好情绪的人数减坏情绪的人数,问这个函数是否合法。$n\le10^5$
  • 题解:先 $dfs$ 一遍记录一下子树的 $p$ 和。注意到一棵子树的根节点的好情绪的人一定大于其儿子的好情绪的人的和,再 $dfs$ 一遍判断即可。注意判断 $abs(h)>p$ 的情况即可。

D

  • 题意:给定两个序列 $a_n,b_n(n\le2\cdot10^5)$ ,定义一种操作选择一个点 $i$ ,将 $a_i$ 加入答案中,如果 $b_i\not =-1$ 则$a_{b_i}+=a_i$ ,每个点恰好被选择一次,问最后答案最大值为多少。$b_i$ 不构成环。
  • 题解:题目显然是一个多棵树的情况。如果一个点的儿子能够通过一系列的操作使得自己的值 $>0$,那么这个儿子的操作一定在父亲的前面会更优,否则则在父亲的后面,通过 $topo$ 序输出方案即可。

E

  • 题意:
  • 题解:
2020-2021/teams/farmer_john/2sozx/codeforces_round_660_div._2.1596174534.txt.gz · 最后更改: 2020/07/31 13:48 由 2sozx