[bzoj 3696] 化合物

一棵有根树. 若个不同的点 i,j 到它们 LCA 的距离分别x,y, 则 A[i][j] = x xor y. 对k=0,1,..., 求出 A[i][j]=k 的 (i,j) 的数目. (i,j),(j,i)算作同一个. (节点数n≤10^5, 最大深度h≤500) 的暴力DP是很显然的, 该怎么优化一下呢?

异或的卷积......好像在哪里听说过......然后去学了一下FWT......

FWT就是每一维长度为2的多维循环卷积. 代码见后面.

出题人要我 "输出到第一个不为零的数为止", 有点奇怪诶. 去题解里找一找输出格式, 然后......

暴力就可以了?

暴力892ms, FWT 2712ms.

据说出题人的标算是FWT. -_-b

一时没想到怎么卡掉暴力......也许暴力的时间复杂度是有保证的?

FWT

typedef long long ll;

const int N = 1e5 + 1, H = 513;

template<typename T>
struct Poly
{
	T a[H];
	void FWT(int n, bool d=false)
	{
		rep (i, 0, n) rep (j, 0, 1<<n)
			if (j & 1<<i)
			{
				int t = a[j];
				a[j] = a[j ^ 1<<i] - t;
				a[j ^ 1<<i] += t;
			}
		if (d)
		{
			n = 1<<n;
			rep (i, 0, n) a[i] /= n;
		}
	}
	void shift(int n)
	{
		per (i, n, 1) a[i] = a[i-1];
		a[0] = 0;
	}
};
Poly<int> F[N];
Poly<ll> tmp;

ll ans[N];
vector<int> adj[N];

int dfs(int u)
{
	int mx = 0;
	rep (i, 0, adj[u].size())
	{
		int v = adj[u][i], h = dfs(v);
		mx = max(mx, h);
		F[v].shift(h);
	}
	++mx;
	int s = 1;
	while ((1<<s) < mx) ++s;
	int n = 1<<s;
	rep (i, 0, n) tmp.a[i] = 0, F[u].a[i] = 1;
	rep (i, 0, adj[u].size())
	{
		int v = adj[u][i];
		F[v].FWT(s);
		rep (j, 0, n) tmp.a[j] += 1LL * F[u].a[j] * F[v].a[j], F[u].a[j] += F[v].a[j];
	}
	tmp.FWT(s, 1);
	rep (i, 0, n) ans[i] += tmp.a[i];
	F[u].FWT(s, 1);
	return mx;
}

int main()
{
	int n;
	scanf("%d", &n);
	rep (i, 2, n+1)
	{
		int p;
		scanf("%d", &p);
		adj[p].push_back(i);
	}
	int h = dfs(1), s = 1;
	while ((1<<s) < h) ++s;
	s = 1<<s;
	while (!ans[--s]) ;
	rep (i, 0, s+1) printf("%lld\n", ans[i]);
	return 0;
}

Brute Force

typedef long long ll;

const int N = 1e5 + 1, H = 513;

int F[N][H];

ll ans[N];
vector<int> adj[N];

int dfs(int u)
{
	int mx = 1;
	F[u][0] = 1;
	rep (i, 0, adj[u].size())
	{
		int v = adj[u][i], h = dfs(v);
		rep (j, 1, h+1) rep (k, 0, mx)
			ans[j ^ k] += 1LL * F[v][j-1] * F[u][k];
		rep (j, 0, h)
			F[u][j+1] += F[v][j];
		mx = max(mx, h+1);
	}
	return mx;
}

int main()
{
	int n;
	scanf("%d", &n);
	rep (i, 2, n+1)
	{
		int p;
		scanf("%d", &p);
		adj[p].push_back(i);
	}
	int h = dfs(1), s = 0;
	while ((1<<s) < h) ++s;
	s = 1<<s;
	while (!ans[--s]) ;
	rep (i, 0, s+1) printf("%lld\n", ans[i]);
	return 0;
}