文章
215
标签
3
分类
3
主页
分类
标签
归档
友链
爱飞鱼的blog
树上连通块计数
搜索
主页
分类
标签
归档
友链
树上连通块计数
发表于
2023-12-21
|
更新于
2025-12-13
|
ICPC
|
浏览量:
树上连通块计数
《解决树上连通块问题的一些技巧和工具》 学习笔记 - evenbao - 博客园 (cnblogs.com)
文章作者:
WTY
文章链接:
https://my-mathmaster-github-io.vercel.app/posts/254db057.html
版权声明:
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议。转载请注明来源
爱飞鱼的blog
！
上一篇
欧拉路
欧拉路 构造题中的欧拉回路 | tyqtyq 的博客 2018的国家集训队论文《欧拉图相关的生成与计数问题探究》 [Tricks] 记各类欧拉回路问题 - 樱雪喵 - 博客园 欧拉路径是满足恰经过所有边一次的通路 欧拉回路是起点和终点相同的一条欧拉路径. 判别法则： 有向图存在欧拉回路: G中所有度数非0的点是强连通的，且所有点入度均等于出度. 有向图存在欧拉通路: 将边看成无向边后，G中所有度数非0的点是连通的。 最多只有一个点入度比出度大 1，作为欧拉通路的起点 最多只有一个点出度比入度大 1，作为欧拉通路的终点 其他所有点入度均等于出度 无向图存在欧拉回路: G中所有度数非0的点是连通的且所有点度数均为偶数. 无向图存在欧拉通路: G中所有度数非0的点是连通。并且G中恰好存在0或2个奇度点。 其他所有点度数均为偶数。那两个奇度点中, 一个作为欧拉通路之起点, 另一个作为终点. 算法流程：感性理解：先找一条起点到终点的通路，然后不断回溯找环。 先用充要条件也就是度数和连通性去判断是不是存在欧拉路...
下一篇
CCPC2023秦皇岛
CCPC2023秦皇岛 C.题意：给定一个字符串，多次区间询问给定一个子串。问有多少种方案删掉最短的区间使得子串变成回文串 Sol：考虑每次询问可以独立处理，当然并不是指把子串单独提出来，而是按顺序正常回答。 一个关键的点是，考虑如果第一个字符和最后一个字符不一样，那一定要删一个，依次推理下去，我们可以得到应该保留最长回文前缀或最长回文后缀。 再考虑如果第一个字符和最后一个字符一样，那我们类双指针缩小删除区间，直到两边不一样。此时又回归到第一种情况。 根据上面这个观察，我们得到获得最小删除代价的做法： 对于一个区间[l, r] 我们首先可以先让首尾相同字符不断相 消, 最后剩余区间[x, y], 如果这个区间为空则为回文串。这一部分等价于求原串后缀l 和反串后缀n − r + 1 的最长公共前缀( LCP ), 再对区间长度取min。 如果不为回文串, 那么str[x]=str[y]str[x] = str[y]str[x]=str[y], x, y 其中之一会被删除。 删除最少长度, 等价于保留最多长度, 即保留x 开头的一个 回文串或y...
WTY
理性思考，和平交流
文章
215
标签
3
分类
3
Follow Me
目录
1.
树上连通块计数
最新文章
贪心
2024-12-22
Z函数与扩展KMP算法详解 - 以CF126B为例
2024-12-21
Codeforces Round 895 (Div. 3)
2024-12-16
可持久化字典树（Trie）
2024-12-16
网格图上问题
2024-12-15
搜索
数据加载中
