[BZOJ3522][Poi2014]Hotel 树形DP


原题链接
暴力枚举中心点即可.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 5023
using namespace std;
typedef long long ll;
int n,head[N],to[N<<1],nxt[N<<1],tot;
inline void add(int x,int y)
{
    to[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
int sum1[N],tsum[N];
void dfs(int x,int pre,int deep)
{
    tsum[deep]++;
    for(int i=head[x];i;i=nxt[i])if(to[i]!=pre)dfs(to[i],x,deep+1);
}
ll ans,sum2[N];
int main()
{
    cin>>n;
    int i,x,y,j;
    for(i=1;i<n;++i)
    {
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }
    for(x=1;x<=n;++x)
    {
        for(i=head[x];i;i=nxt[i])
        {
            y=to[i];
            dfs(y,x,1);
            for(j=1;tsum[j];++j)ans+=(ll)tsum[j]*sum2[j];
            for(j=1;tsum[j];++j)sum2[j]+=(ll)tsum[j]*sum1[j];
            for(j=1;tsum[j];++j)sum1[j]+=tsum[j];
            for(j=1;tsum[j];++j)tsum[j]=0;
        }
        memset(sum1,0,sizeof sum1);
        memset(sum2,0,sizeof sum2);
    }
    cout<<ans;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注