当我跨过沉沦的一切
向着永恒开战的时候
你是我的军旗

标签 树形 DP 下的文章

对于两棵树 T_1, T_2,定义它们的交 T_1 \cap T_2 是它们的边集的交形成的森林,k(T_1 \cap T_2)表示这个森林的连通块个数,求下列三种问题之一:

  1. 给定 T_1, T_2,求 y^{k(T_1\cap T_2)}

  2. 给定 T_1,求 \sum_{T_2}y^{k(T_1\cap T_2)}

  3. 给定 n,求 \sum_{T_1}\sum_{T_2}y^{k(T_1\cap T_2)}

其中 n \leq 10^5 ,上面的 sum 是对所有 n^{n-2} 种可能的树求和。答案对 998244353 取模。

orzrqy

READ MORE

榕树还是当年的榕树,你却不是当年的你了……

先点名表扬下这个题面,写的也太优美了吧 QAQ ...

假设我们只需要判断 1 号点能否成为最后的答案,用 f_i 表示取完 i 所在的子树的所有点后榕树的心离 i 的最近距离,那么答案即求 [f_1 = 0].

考虑 f_u 怎么求,最难消去的孩子是 \max (siz_v) (v \in son_u) 的孩子 v ,可以用其他子树的 siz 来填补这棵子树。代码中,另一部分的大小表示为 half ,这一部分表示为 f[max]

对于不以 1 为根的情况,可以把根节点到当前点 u 的路径缩成一个点来考虑,可以上下 DP 。

READ MORE

我们先考虑一个 O(n \times 2^{n-m+1}) 的做法:每次硬点每个限制的左端点选或不选,然后树形 DP 。

考虑每次树形 DP 时不一样的点是很少的,可以建出一个虚树把那些点提出来,需要注意的是最好把整棵树的根同时硬点为虚树的根,可以少判一些情况。

然后对于不在虚树上的部分预先 DP 出来,可以理解为一个关于某一个虚点的 DP 值(取或不取)的二元一次函数,然后每次硬点就只需要跑虚树即可,复杂度 O(n + (n - m + 2) \times 2^{n - m + 1})

READ MORE