题意简述
给定一棵 $n$ 个节点的，以 $1$ 为根的有根树，请按升序输出所有满足下面要求的正整数 $k$：
- 这棵树可以被划分为 $k$ 个节点数目相同的连通块。
数据范围：$2\le n\le 3\times 10^6$。
解析
首先，我们需要找出可能成为连通块节点数目的所有正整数，记为 $d$。
显然，$d$ 必须是 $n$ 的因数。
如果将这部分的复杂度压缩至根号，不要忘记将数组排好序！！ 我不会告诉你我为什么要提醒这一条
然后，降序枚举 $d$（对于 $1$ 和 $n$ 我们可以不经判断直接输出），判断树可否分为若干大小都为 $d$ 的连通块。
方法使用贪心，具体实现如下：
- 对整棵树进行 DFS，同时维护布尔值 $Ans$（初始为 $1$）。对每个节点记录在其子树中且与该节点位于同一连通块的节点数，保存为 $sz$ 数组。为表述方便，记每个连通块的大小为 $sz_0$（与当次的 $d$ 相等）。
- 搜索到节点 $u$ 时，如果 $Ans=0$ 那么将 $sz_u$ 归零后返回（避免无用初始化）。
- 如果 $Ans=1$，搜索 $u$ 的每个子节点 $v$。
- 返回时：
- 如果 $sz_u\gt sz_0$，那么将 $Ans$ 设为 $0$ 并返回；
- 如果 $sz_u=sz_0$，那么直接返回；
- 如果 $sz_u\lt sz_0$，那么将 $sz_{fa_u}$ 加上 $sz_u$ 并返回（$fa_u$ 为 $u$ 的父亲）。
- 无论哪种情况，返回前必须将 $sz_u$ 设为 $0$。
- 整棵树搜完后，判断 $Ans$ 是否仍然为 $1$。若是，则 $\frac{n}{sz_0}$ 为答案。
接下来证明这种方法的正确性。
假设这是我们第一次割下来的，大小为 $sz_0$ 的块。如果我们不割它，那么显然没有别的解法。所以，有块，一定割。
再假设在一棵子树中能割的块都割完了，但剩下的大小大于 $sz_0$。显然，如果各个子节点还能割的话一定就割了，所以现在各个子节点的 $sz$ 值均小于 $sz_0$。我们不能抛下任意一棵子树（否则大小就不等于 $sz_0$ 了），所以此时一定无解。那么对于大小小于 $sz_0$ 的 $sz$ 值，我们只能选择把这个节点的剩余连通部分交给父节点去割。
所以每次验证 $d$ 是否可行都需要一次 $\mathcal{O}(n)$ 的 DFS。那么 $n$ 的正整数因数个数到底有多少呢？
这个答案有个相当宽松的上界，$2\sqrt{n}$。但在 $n\le 3\times 10^6$ 的条件下，较大的 $n$ 显然不可能达到这个值。事实上，题目范围内含有最多正整数因子的数为 $2\ 882\ 880$，含有 $336$ 个因子。而题目的时间限制是 10 秒，所以我们的算法肯定可以通过！（亲测，当 $n=10^3$ 时，$\mathcal{O}(n^3)$ 的区间 DP 关同步流甚至跑不到 500ms）
参考代码
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define _ 507
int d[_];//存n的因子
#define N 3000007
int cnt,head[N];
struct qwq{int v,nxt;}edge[N];//链式前向星存边
inline void AddE(int u,int v){
edge[++cnt]={v,head[u]};
head[u]=cnt;
}
bool Ans;//是否有解
int sz[N];//剩余块大小
inline void dfs(int u,int fa,int sz0){
sz[u]++;//自己也得算
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].v;
dfs(v,u,sz0);
if(!Ans) {sz[u]=0;return;}//记得归零
}
if(sz[u]>sz0) {sz[u]=0;Ans=0;return;}//记得归零
if(sz[u]==sz0) {sz[u]=0;return;}//记得归零
sz[fa]+=sz[u];sz[u]=0;//记得归零
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int n,m=0;
cin>>n;
for(int i=2;i*i<=n;i++)//根号判因数
if(n%i==0){
d[++m]=i;
if(i*i!=n) d[++m]=n/i;
}
sort(d+1,d+m+1);//如果根号判因数一定要记得sort！！
for(int i=2,a;i<=n;i++) cin>>a,AddE(a,i);//父节点到子节点
cout<<1<<' ';//显然
for(int i=m;i;i--){
sz[0]=0,Ans=1;dfs(1,0,d[i]);//d为连通块大小
if(Ans) cout<<n/d[i]<<' ';//输出的为连通块个数
}
cout<<n<<'\n';//显然
return 0;
}感谢您的阅读！