[POI2014]HOT-Hotels

考虑先做一个(O(n^2) 的 dp)
(f[i][j])表示在(i)的子树中，距离当前点为(j)的点数
(g[i][j])表示在(i)的子树中，两个点(lca)的距离为(d),他们的(lca)到(i)距离为(d - j)的点对数。
那么怎么转移？
(ans += g[i][0],ans += g[i][j] * f[son][j - 1],f[i][j] += f[son][j - 1],g[i][j] += g[son][j - 1] + f[u][j] * f[son][j - 1])
那么可以用长链剖分优化到(O(n))

[POI2014]HOT-Hotels

#include<iostream>
#include<cstdio>
#define ll long long
#define N 5005

ll n,head[N],*f[N],*g[N],p[N << 2],*o = p,ans;

ll cnt;

struct E{int to,next;}e[N << 1];

inline void add(int x,int y){
	e[++cnt].to = y;
	e[cnt].next = head[x];
	head[x] = cnt;
}

ll dep[N],son[N];

inline void dfs(int u,int f){
	dep[u] = dep[f] + 1;
	for(int i = head[u];i;i = e[i].next){
		int v = e[i].to;
		if(v == f)
		continue;
		dfs(v,u);
		if(dep[v] > dep[son[u]])
		son[u] = v;
	}
	dep[u] = dep[son[u]] + 1;
}

void dp(int x, int fa) {
	if (son[x])
		f[son[x]] = f[x] + 1, g[son[x]] = g[x] - 1, dp(son[x], x);
	f[x][0] = 1, ans += g[x][0];
	for (int i = head[x];i;i = e[i].next){
			ll y = e[i].to;
			if (y != fa && y != son[x]) {
			f[y] = o, o += dep[y] << 1, g[y] = o, o += dep[y] << 1;
			dp(y, x);
			for (int i = 0; i < dep[y]; i++) {
				if (i) ans += f[x][i-1] * g[y][i];
				ans += g[x][i+1] * f[y][i];
			}
			for (int i = 0; i < dep[y]; i++) {
				g[x][i+1] += f[x][i+1] * f[y][i];
				if (i) g[x][i-1] += g[y][i];
				f[x][i+1] += f[y][i];
			}
		}
	}
}

int main(){
	scanf("%lld",&n);
	for(int i = 1;i <= n - 1;++i){
		ll x,y;
		scanf("%lld%lld",&x,&y);
		add(x,y);
		add(y,x);
	}
	dfs(1,0);
	f[1] = o,o += dep[1] << 1,g[1] = o,o += dep[1] << 1;
	dp(1,0);
	std::cout<<ans<<std::endl;
}