BZOJ3522: [Poi2014]Hotel

题解:

考虑三个点在树上的形态:

(1)成一条链(其实就是中心是三个点中的一个点)

(2)存在一个唯一中心连接三个点，且中心到三个点的路径除了中心之外不相交

(定义自己脑补一下吧...)

显然只有在(2)情况下,并且唯一中心到三个点的路径长度相等才能满足条件.

我们直接枚举唯一中心,以其为根做有根树,则三个点必须分布在不同的子树中,且深度相同.

这个就很容易搞了,看代码搞搞就行了.

代码:

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef long long ll;
#define N 5010
int head[N],next[N<<1],end[N<<1];
inline void addedge(int a,int b){
    static int q=1;
    end[q]=b;
    next[q]=head[a];
    head[a]=q++;
}
inline void make(int a,int b){
    addedge(a,b);
    addedge(b,a);
}
 
int sum1[N];
ll sum2[N];
struct Array{
    int a[N],t[N],tclock;
    inline int operator[](int x){
        if(t[x]!=tclock){
            t[x]=tclock;
            a[x]=0;
        }
        return a[x];
    }
    inline void add(int x){
        if(t[x]!=tclock){
            t[x]=tclock;
            a[x]=0;
        }
        ++a[x];
    }
}temp;
 
int max_dep;
inline void dfs(int x,int fa,int dep){
    temp.add(dep);
    max_dep=max(max_dep,dep);
    for(int j=head[x];j;j=next[j])
        if(end[j]!=fa)
            dfs(end[j],x,dep+1);
}
 
int main(){
#ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
#endif
    int n;
    scanf("%d",&n);
    int i,j,k,a,b;
    for(i=1;i<n;++i){
        scanf("%d%d",&a,&b);
        make(a,b);
    }
    ll ans=0;
    int son;
    for(i=1;i<=n;++i){
        memset(sum1,0,sizeof sum1);
        memset(sum2,0,sizeof sum2);
        for(son=1,j=head[i];j;j=next[j],++son){
            ++temp.tclock;
            max_dep=0;
            dfs(end[j],i,1);
            for(k=1;k<=max_dep;++k){
                if(son>=3)
                    ans+=sum2[k]*temp[k];
                sum2[k]+=temp[k]*sum1[k];
                sum1[k]+=temp[k];
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}