嘟嘟嘟



这题想了半天，搞出了一个\(O(10 * d * n)\)（\(d\)为\(n\)的约数个数）的贪心算法，就是能在子树内匹配就在子树内匹配，否则把没匹配的都交给父亲，看父亲能否匹配。交上去开了O2才得了60分。按讨论中的方法卡常后还是A不了，就放弃了。



正解需要推一个结论，就是一棵树能被分成\(x\)个大小相同的联通块，必须满足至少有\(\frac{n}{x}\)个子树的大小为\(x\)的倍数。

证明啥的yy一下就好啦……

想到这个结论后，我还是没想出复杂度更优的算法……最后看题解才知道，你开个桶记录子树大小，每次枚举倍数就能把\(n\)降成\(\sqrt{n}\)了……



啊忘说了，讨论中的卡常就是根据题中树的构造方法，把dfs改成逆序扫一遍，减小常数。

#include<cstdio>

#include<iostream>

#include<cmath>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<vector>

#include<stack>

#include<queue>

using namespace std;

#define enter puts("")

#define space putchar(' ')

#define Mem(a, x) memset(a, x, sizeof(a))

#define In inline

typedef long long ll;

typedef double db;

const int INF = 0x3f3f3f3f;

const db eps = 1e-8;

const int maxn = 1.2e6 + 5;

const int NUM = 19940105;

inline ll read()

{

  ll ans = 0;

  char ch = getchar(), last = ' ';

  while(!isdigit(ch)) last = ch, ch = getchar();

  while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();

  if(last == '-') ans = -ans;

  return ans;

}

inline void write(ll x)

{

  if(x < 0) x = -x, putchar('-');

  if(x >= 10) write(x / 10);

  putchar(x % 10 + '0');

}

int n, fa[maxn];

struct Edge

{

  int nxt, to;

}e[maxn];

int head[maxn], ecnt = -1;

In void addEdge(int x, int y)

{

  e[++ecnt] = (Edge){head[x], y};

  head[x] = ecnt;

}

int num[maxn], cnt = 0;

In void init(int n)

{

  for(int i = 1; i * i <= n; ++i)

    if(n % i == 0)

      {

	num[++cnt] = i;

	if(i * i < n) num[++cnt] = n / i;

      }

  sort(num + 1, num + cnt + 1);

}

int ans;

int dp[maxn];

In bool dfs(int now, int _f)  //我的O(n)贪心

{

  for(int i = 1; i <= n; ++i) dp[i] = 1;

  for(int i = n; i; --i)

    {

      if(dp[i] > ans) return 0;

      if(dp[i] == ans) dp[i] = 0;

      dp[fa[i]] += dp[i];

    }

  return 1;

}

int siz[maxn], tot[maxn];

In bool judge(int x)

{

  int ret = 0;

  for(int i = x; i <= n; i += x) ret += tot[i];

  return ret >= n / x;

}

In void solve()

{

  fill(siz + 1, siz + n + 1, 1);

  fill(tot + 1, tot + n + 1, 0);

  for(int i = n; i; --i)

    {

      siz[fa[i]] += siz[i];

      ++tot[siz[i]];

    }

  for(int i = 1; i <= cnt; ++i)

    {

      ans = num[i];

      if(judge(num[i])) write(ans), enter;

    }

}

int main()

{

  n = read(); init(n);

  for(int i = 2; i <= n; ++i) fa[i] = read();

  puts("Case #1:");

  solve();

  for(int t = 1; t <= 9; ++t)

    {

      printf("Case #%d:\n", t + 1);

      for(int i = 2; i <= n; ++i) fa[i] = (fa[i] + NUM) % (i - 1) + 1;

      solve();

    }

  return 0;

}