Codeforces Round 926
D - Sasha and a Walk in the City
dp，主要难点在于设状态。
发现子树内一旦存在一个点，到当前子树的根节点路径上有两个危险点，那么除了那条链所属的子树，其他的点就都不能选了。所以把这个性质放进状态，设 \(f_{u, 0/1}\) 表示以 \(u\) 为根的子树内，是否存在一条到 \(u\) 经过两个危险点的链。
那么转移不难。
\[f_{u, 0} = (\prod _{v \in son_u} f_{v, 0}) + 1 \\ f_{u, 1} = \sum_{v \in son_u} f_{v,0}-1+f_{v,1} \]这做不出来？？？？？？
E - Sasha and the Happy Tree Cutting
发现性质就是弱智题了。
通过虚树可以证明，本质不同的边是 \(O(k)\) 级别的。
所以直接算出所以本质不同的边，暴力 dp 即可。
F - Sasha and the Wedding Binary Search Tree
直接在树上考虑有点麻烦的。
发现可以把题目给的 BST 中序遍历求出来，然后给 -1 填数，要求不降。
然后弱智题，对 -1 连续段算组合数即可。
标签：Tree,Codeforces,son,202402,解题,危险点,Sasha,dp From： https://www.cnblogs.com/harqwq/p/18018172