Luogu5904 [POI2014] HOT-Hotels 加强版

发表于 分类于 ， ， 阅读次数：

题意：给出一棵 个点的树，求有多少组无序三元组 满足 两两之间的距离都相等。

，时限 。

考虑将一组合法的 放到有根树上会如何，如图：

考虑在右侧最浅点（黑色）处统计。

设 为 子树内距离 为 的点数。（一个点）

设 为 子树内如上图灰框内的方案数。（两个点）

假设新加入的子树为 ，则有：

1
2
3
4
5
6
7
ans += c[u][k+1]*g[v][k]+c[v][k]*g[u][k+1];
	// 可以先单后双，也可以先双后单
g[u][k-1] += g[v][k];
	// 直接延长一个分支内的点对
g[u][k+1] += c[u][k+1]*c[v][k];
	//让两个不同分支合并
c[u][k+1] += c[v][k];

发现 不会超过 ，长剖即可做到 。