用树形DP+状压维护树上操作的计数问题：0902T3
用树形dp+状压维护树上操作的计数问题：0902T3
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132647373
发现操作数 ，可以考虑对操作进行 状压 。
然后找找性质，发现要么删掉一棵子树，要么进去该子树。可以视为每种操作有两种情况。
然后分讨一下当前该如何转移。
树形dp的顺序：
-
合并子树
-
考虑当前往上的边的方向
然后发现只需要记住最早一次保留操作就行。
对于连通块大小的限制，就看一下当前操作之前有多少个子树内删掉操作。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-09-18
对于每种情况分别统计概率来计算期望+树上连通块统计：ARC165E
对于每种情况分别统计概率来计算期望+树上连通块统计：ARC165E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132971902 https://atcoder.jp/contests/arc165/tasks/arc165_e 考虑一个常见套路，我们对每个连通块统计其概率，设为 p(T)p(T)p(T) ，则答案为 ∑∣T∣>kp(T)\sum_{|T|>k} p(T) ∣T∣>k∑p(T) 可以想成对于每个大小大于 kkk 的连...
2023-11-14
枚举连通块拆贡献+容斥：ABC321G
枚举连通块拆贡献+容斥：ABC321G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133266690 https://atcoder.jp/contests/abc321/tasks/abc321_g 这种题都没看出来我要去退役了 看完题目，可以获得： 期望、连通块：显然拆贡献啊！ n≤17n\le 17n≤17 ：这不明显状压？结合前面连通块，就是枚举连通块啊！ 继续分析第2点，17这么小，显然枚举子集。为啥枚举？计数题只有容斥这个套路啊！...
2024-10-07
1006C简单题（计数式子的组合意义 + DP式子联立）
1006C简单题（计数式子的组合意义 + dp式子联立） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142740338 http://cplusoj.com/d/senior/p/SS241006C 对于这个式子，我们可以从它的组合意义入手。 假设我们有 n+1n+1n+1 个白球要染色，中间有一个绿球，绿球左边有 aaa 个红球，右边有 bbb 球。染完后绿球左边每个白球有 xxx 的贡献，右边每个白球有 yyy 的贡献。 但接下来怎么做呢？这列出来...
2021-12-01
【Loj #10104. 「一本通 3.6 练习 5」Blockade】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15629936.html 题目链接 首先这个点删去之后必然与剩下 n−1n-1n−1 个点失去相连。 如果这个点能使其它点失去相连，说明这个点为割点。 然后统计一下每个儿子与父亲的影响即可。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666...
2021-11-24
【P1270 “访问”美术馆】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15600574.html 题目链接 典型的树形dp。 设 dp(x,i)dp(x, i)dp(x,i) 表示 xxx 的子树内逗留 iii 秒的作品最大值。 dp(x,i)=maxy∈xmaxi=0smaxj=2×zidp(y,j−2×z)−dp(x,j−i)dp(x, i)=\max_{y\in x}\max_{i=0}^s\max_{j=2\times z}^i dp(y,j-2\times z)-dp(x,j-i) dp(x,i)=y...
2021-12-01
【Loj #10099. 「一本通 3.6 例 2」矿场搭建】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15630249.html 题目链接 我们先对于有向图缩点，变成一棵树。 然后我们对于每个树上且在原图中的分割点节点所对应原图中的连通块考虑。 假设这里没有割点，很明显，只需要放2个出口即可。 如果有一个割点，说明这个点是树上的叶子节点，需要放1个出口。 如果有两个或以上的割点，无论哪个割点被割，都可以往另一个方向逃，所以这个连通块不用放。 Code 1234567891011121314151617181920212223242526272829...