参考:p_z_y 的博客,YellowBean 的代码启示。 尽量写短点。 dsu on tree 模板题:CF600E Lomsat gelral。 题意: 有一棵 $n$ 个结点的以 $1$ 号结点为根的有根树。 每个结点都有一个颜色,颜色是以编号表示的, $i$ 号结点的颜色编号为 $c_i$。 如果一种颜色在以 $x$ 为根的子树内出现次数…
题意 题目链接。 给出一颗树,走到叶子节点后可以回到它的第 $k$ 祖先,求最多可以访问多少叶子节点。 解析 定义 $f_{i}$ 为从 $i$ 节点开始走,最后走回到 $i$ 节点的贡献,$g_i$ 为从 $i$ 节点开始走,最后不用回到 $i$ 节点的最大贡献。 先预处理出从每个点开始走可以回到的最高点,对于叶子节点,初始先将其贡献打到其第 $…
题意 题目链接。 有一棵红树和一棵蓝树,结点相同而边不同。双方各在某一点,只能在自己颜色的树上移动,红方先手。红方需要最大化游戏轮数,蓝方则需要最小化游戏轮数。求最终游戏轮数。 解析 首先发现,如果存在一条连接 $u,v$ 的红边,且 $u,v$ 两点在蓝树上的距离不小于 $3$,则若红方到达其中某一点且蓝方下一步抓不住他,游戏就会进行无限轮。画图…
题意 题目链接 给定一棵树,每次询问给出一个点 $u$ 和深度 $d$,询问深度为 $d$ 的点中有多少个点祖先包含 $u$。 解析 考虑用一个时间戳,记录每一个点的入栈时间 $in_i$ 和出栈时间 $out_u$,发现每一个符合条件的点 $x$ 满足 $in_u \le in_x < out_u$。由此,用 vector 维护每一层所有点…
题意 题目链接 树上的棋子博弈,每个点有权值。你可以添加一条边以试图反败为胜,不同的加边方法根据权值有一个代价,需要最小化这个代价。 解析 我们首先定义一个结点先手必败是 lose,先手必胜是 win,容易发现,叶子结点一定是 lose,然后对于每一个非叶子结点,只要它有一个儿子是 lose,它就是 win,否则,该结点也是 lose。一遍 d…
题意 题目链接 有一棵树有粉点有黑点,从根开始走,每走到一个点都会改变颜色。求一种方案使所有点变成黑色。 解析 我们考虑使用递归的方式寻找答案。假设一棵树的深度只有 $2$,那么我们只需要从根开始,找到粉点,走过去再回来,重复几次,就可以使下一层的所有点变为黑色。 以这种方式一层一层染色,最后对于根节点,如果为黑色不用处理,否则,走下去,走回来,再…