题意 题目链接。 给你一棵树，你可以在树上连两条边，这两条边会分别形成两个环，要求这两个环没有任何相同的边或结点，求连边的方案数。 解析 蛮有趣的一个树形 dp。 考虑对于所有的连边方案，在这四个点的 LCA 处进行统计。那么我们考虑对于一个点 $u$ ，有多少方案是以其为 LCA 的，发现共有以下几种情况： $2-2$ 结构：在 $u$ 的两棵不…

参考：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$，那么我们只需要从根开始，找到粉点，走过去再回来，重复几次，就可以使下一层的所有点变为黑色。 以这种方式一层一层染色，最后对于根节点，如果为黑色不用处理，否则，走下去，走回来，再…