luogu P3565 [POI2014]HOT-Hotels 普通的树形dp

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=10005;
int e[N],ne[N],idx,h[N];
int n;
int cnt,bian[N],deep,tot[N],c1[N],c2[N];
long long ans;
void add(int a,int b)
{
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx++;
}
void dfs(int u,int fa,int d)
{
	deep=max(deep,d);
	//深度为d 的点的数量
	tot[d]++;
	for (int i=h[u]; ~i; i=ne[i])
	{
		int v=e[i];
		if (v==fa)
			continue;
		dfs(v,u,d+1);
	}
}
int main()
{
	memset(h,-1,sizeof h);
	cin>>n;
	for (int i=1; i<n; i++)
	{
		int a,b;
		cin>>a>>b;
		bian[a]++;
		bian[b]++;
		add(a,b);
		add(b,a);
	}
	//以当前点为根节点
	//所选的三个点的lca必须相同
	for (int i=1; i<=n; i++)
	{
		//如果相连的边 小于3，也就是子树的分支小于三个，就选不出符合要求的
		if (bian[i]<3)
			continue;
		memset(c1,0,sizeof(c1));
		memset(c2,0,sizeof(c2));
		//以当前点为根节点
		for (int j=h[i]; ~j; j=ne[j])
		{
			int v=e[j];
			//遍历当前子树
			dfs(v,i,1);
			//选深度
			for (int d=1; d<=deep; d++)
			{
				//在之前的选两个，当前新生成的选一个
				ans+=c2[d]*tot[d];
				//更新完答案之后，当前树的这一层视为已经访问过，更新选两个的情况
				//就是 之前的选一个，当前子树的选一个
				c2[d]+=c1[d]*tot[d];
				//更新总数
				c1[d]+=tot[d];
			}
			//清空
			memset(tot,0,sizeof(tot));
		}
	}
	printf("%lld",ans);
	return 0;
}