[POI2014]HOT-Hotels

代码：

#include<bits/stdc++.h>
using namespace std;
int n,d[5005],dep[5005],son[5005];
int to[10005],ne[10005],h[10005],cnt;
inline void link(int x,int y){
	to[++cnt]=y;
	ne[cnt]=h[x];
	h[x]=cnt;
}
long long *f[5005],*g[5005],p[15005],*o=p,ans;
void dfs(int x,int fa){
	d[x]=d[fa]+1;
	for(int i=h[x];i;i=ne[i]){
		int y=to[i];
		if(y!=fa){
			dfs(y,x);
			if(dep[y]>dep[son[x]])son[x]=y;
		}
	}
	dep[x]=dep[son[x]]+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=h[x];i;i=ne[i]){
		int y=to[i];
		if(y!=fa&&y!=son[x]){
			f[y]=o;o+=dep[y]<<1;g[y]=o;o+=dep[y];
			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("%d",&n);
	for(int i=1;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		link(x,y);link(y,x);
	}
	dfs(1,1);f[1]=o,o+=dep[1]<<1,g[1]=o,o+=dep[1];
	dp(1,1);
	printf("%lld",ans);
	return 0;
}

我看题解里都是把

  f[y]=o;o+=dep[y]<<1;g[y]=o;o+=dep[y];

写成了

  f[y]=o;o+=dep[y]<<1;g[y]=o;o+=dep[y]<<1;

但向下 $dp$ 的时候， $f$ 指针只会向后走，而不会像 $g$ 一样向前走，所以是不是没必要在 $g[x]$ 与 $f[son[x]]$ 之间留出两倍空间