树上连通块计数
整理日期按学习顺序编排，不代表原始发表时间。实际整理于 2026-10-23。
难度为阅读建议，可从 ACM 学习索引 按阶段阅读。
树上连通块计数
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 爱飞鱼的blog！
相关推荐
整理日期：2026-04-03
DFS order
DFS order [P9872 EC Final 2021] DFS Order - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) [P9669 ICPC2022 Jinan R] DFS Order 2 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) [P9669 ICPC2022 Jinan R] DFS Order 2 题解 - 洛谷专栏 (luogu.com.cn) DFS Order 3 - Problem - QOJ.ac DFS Order 4 - Problem - QOJ.ac DFS Order 5 - Problem - QOJ.ac
整理日期：2026-05-15
DFS序专题
DFS序专题 NC13611 https://ac.nowcoder.com/acm/problem/13611 题意：要求树上任意两点相同颜色之间的路径上的点也是相同颜色，k种颜色，求方案数 Solution：原问题等价于将树分割成若干连通块且相互之间颜色不同 其实是道数论题。 题意可以转化为将树分割为不超过 kkk 个连通块，每个连通块颜色不同。若将树分割为 iii 个连通块，则需要删去 i−1i-1i−1 条边，故方案数为 Cn−1i−1\mathrm{C}_{n-1}^{i-1}Cn−1i−1 。同时，要从 kkk 种颜色中选出 iii 中颜色染色，而且是有顺序的，故方案数为 Aki\mathrm{A}_{k}^{i}Aki 。 综上，总的方案数为： ans=∑i=1min(n,k)Cn−1i−1Akians= \sum_{i=1}^{\min(n,k)}\mathrm{C}_{n-1}^{i-1}\mathrm{A}_{k}^{i}ans=∑i=1min(n,k)Cn−1i−1Aki 可以线性求逆元，枚举 iii 实现。...
整理日期：2026-05-14
xiaosaitmp
题面翻译 给你一个NNN个节点的树，求一个1⋯N1\cdots N1⋯N的排列(p1,p2,⋯pN)(p_1,p_2,\cdots p_N)(p1,p2,⋯pN) ，使得∑dist(i,pi)\sum dist(i,p_i)∑dist(i,pi)最大。 求这样的排列的个数。答案对109+710^9+7109+7取模。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include <iostream>#include <cstdio>#include <cstring>#include <vector>#include <cmath>using namespace std;typedef long long ll;typedef pair<int,int>ttfa;inline ll...
整理日期：2026-09-15
为什么树的dfs不需要vis数组，只需要维护父节点就可以？
无向图无环的，无环的图总是可以展成树的形式。 然后考虑无向图，顶多有回边指向父节点。不可能有回边指向祖先。更不可能有横向边，因为无环啊。所以只需要考虑指向父节点的回边就可以无需使用Vis。
整理日期：2026-09-19
二叉树已经知道先序中序推后序
https://www.acwing.com/problem/content/3601/ 不断找新的先序的根节点，根据位置切割中序，根据中序左右子树大小反切割先序，找到左子树对应的先序中序，然后递归处理 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include<stdio.h>#include<vector>#include<map>#include<algorithm>#include <algorithm>#include <iostream>#include<string>using namespace std;#define ll long long//# define int long long#define ull unsigned long long#define pii pair<int,int>#define...
整理日期：2026-09-20
二叉树扩展先序遍历转中序遍历
利用前序遍历的特性，如果左子树不空，下一个一定是左节点，不然就是# 因为是转中序遍历，就在两次遍历之间输出 12345678910111213141516171819202122232425262728#include <iostream>#include <cstring>#include <algorithm>using namespace std;int k;string str;void dfs(){ if (str[k] == '#') { k ++ ; return; } char r = str[k ++ ]; // 根节点 dfs(); // 左子树 cout << r << ' '; dfs(); // 右子树}int main(){ cin >> str; dfs(); return 0;}
最新文章