bitset+二进制优化

具体分析可以参考https://codeforces.com/blog/entry/98663
简而言之就是可以通过\(O(\frac{C\sqrt C}{w})\)的复杂度判断是否能够获得某种体积

开不同大小bitset

template<int len = 1>
void solve(ll s) {
	if (len <= s) {
		solve<min(len*2,N)>(s);
		return;
	}

当然要c++14及以上才能支持

剪枝

不过感觉这个剪枝可能只对这道题比较有用，当一个子树的大小大于其它的和，那么肯定是这个分一组，剩下的分一组。
具体复杂度分析见https://codeforces.com/blog/entry/119058

科技拉满的一道题。
虽然感觉以后也遇不到，但还是很有意思。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<ctime>
#include<unordered_map>
#include<queue>
#include<bitset>
#include<iostream>
#define A puts("YES")
#define B puts("NO")
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
//const ll mo=1e9+7;
//const int inf=1<<30;
const int N = 1e6 + 5;
int head[N], to[N], nex[N], tot, n, x;
int m;
ll a[N], s[N], ans;
vector<ll> b;

void add(int x, int y) {
	to[++tot] = y; nex[tot] = head[x]; head[x] = tot;
}
bool cmp(ll a, ll b) {
	return a > b;
}
template<int len = 1>
void solve(ll s) {
	if (len <= s) {
		solve<min(len*2,N)>(s);
		return;
	}

	bitset<len> f;
	f[0] = 1;

	for (ll x:b) f |= f << x;
	ll mx = 0;
	fo(i, 1, s) {
		if (f[i]) mx = max(mx, i*(s-i-1));
	}
	ans += mx;

}
void dfs(int x) {
	s[x] = 1; //
	for (int i = head[x]; i; i = nex[i]) {
		int v = to[i];
		dfs(v);
		s[x] += s[v];
	}

	m = 0;

	for (int i = head[x]; i; i = nex[i]) {
		int v = to[i];
		a[++m] = s[v];
	}
	a[++m] = 0;
	sort(a + 1, a + m + 1, cmp);

	if (a[1] >= s[x] / 2) {                                                        
		ans += a[1] * (s[x] - 1 - a[1]);
		return;
	}

	b.clear(); 
	ll l = 0, num;
	fo(i, 1, m-1) {
		if (a[i] != a[i+1]) {
			num = i - l;
			ll j = 1;

			while (j < num) {
				b.emplace_back(j * a[i]);
				num -= j;
				j <<= 1;
			}
			b.emplace_back(num * a[i]);

			l = i;
		}
	}

	solve(s[x]);
}
int main()
{
	//	freopen("data.in","r",stdin);
	//	freopen("data.out","w",stdout);


	std::ios::sync_with_stdio(false);
		
	cin >> n;
	fo(i, 2, n) {
		cin >> x;
		add(x, i);
	}
	dfs(1);
	cout << ans;
	return 0;
}