题目链接

bzoj4543 [POI2014]Hotel

题解

这不是裸地点分嘛 ，我真傻，真的

n^2 这不是是sb题，~滑稽 ~

枚举点转换为无根树，暴力子树中点的深度

计数转移

令a b c d为已知四颗子树，则新来一颗深度为k的点数为e的子树

推下式子

\(new_ans=e*(a*b+a*c+b*c+d*a+d*b+d*c)\)

用s维护 \((a*b+a*c+b*c+d*a+d*b+d*c .....)\)

用cnt维护\((a+b+c+d+e+....)\)

s的转移为 \(s + cnt * tmp\);

代码

#include<algorithm>

#include<cstring>

#include<cstdio>

inline int read() {

    int x = 0,f = 1;

    char c = getchar();

    while(c < '0' || c >'9') {if(c == '-') f = -1;c = getchar();}

    while(c >= '0' && c <= '9') x = x * 10 + c - '0',c = getchar();

    return x * f;

}

int n;

const int maxn = 5007;

struct Node {

    int v,next;

    Node(int a = 0,int b = 0):  v(a),next(b) {};

}edge[maxn << 1];

int num,head[maxn];

inline void add_edge(int u,int v) {

    edge[++num] = Node(v,head[u]);head[u] = num;

}

int dp[maxn][maxn];

int deep[maxn],mx = 0,cnt[maxn],tmp[maxn],s[maxn];

void dfs(int x,int fa) {

    tmp[deep[x]] ++;

    mx = std::max(mx,deep[x]);

    for(int i = head[x];i;i = edge[i].next) {

        int v = edge[i].v;

        if(v == fa) continue;

        deep[v] = deep[x] + 1;

        dfs(v,x);

    }

}

int main() {

    n = read();

    for(int u,v,i = 1;i < n;++ i) {

        u = read() , v = read();

        add_edge(u,v);add_edge(v,u);

    }

    long long int ans = 0;

    for(int i = 1;i <= n;++ i) {

        for(int j = head[i];j;j = edge[j].next) {

            int v = edge[j].v;

            mx = 0;

            deep[v] = 1;

            dfs(v,i);

            for(int k = 1;k <= mx;++ k) {

                ans += s[k] * tmp[k];

                s[k] += tmp[k] * cnt[k];

                cnt[k] += tmp[k];

                tmp[k] = 0;

            }

        }

        memset(s,0,sizeof s);

        memset(cnt,0,sizeof cnt);

    }

    printf("%lld\n",ans);

    return 0;

}