POI2014 HOT-Hotels

发表于 | 分类于 |
字数统计: 624 字

题目链接

题解

一个比较容易证明的结论是：这三个点必然会经过某一个点，并且该点到他们的距离相等。
这样，我们枚举每一个点，然后算一下每层深度有多少个这样的点，计数即可。
这样会有重复，不妨这么考虑：
一个点是“中心点”的前提是他是另外$3$个点的$LCA$。
所以为了避免某$2$个深度相同的点的$LCA$不是当前枚举的点，我们就把每一颗当前枚举点的子树看作是一个集合，集合中深度相同的$2$个点不可同时选取，就转化为了一个组合问题。
假设有$n$个集合，大小分别为要从其中$3$个集合中各选一个元素组成$3$元组个方案数显然是。这些方案数的和就是当前点的答案。然后考虑加入一个集合，要快速得到这个集合的贡献，就要维护其他集合两两乘积的和，把新集合大小乘上去就是新集合的贡献。维护两两乘积的和又需要维护所有集合大小之和，这就是代码里开了$f,g$2个数组的原因。$f$就是集合大小和，$g$就是两两乘积和。
这么做是$O(n^2)$的。
容易被卡。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x; 
}
int n,to[10005],nex[10005],at[10005]={0},cnt=0;
ll ans=0,f[5005],g[5005],d[5005]={0};
//次数1 2 3 
void dfs(int cur,int fa,int de){
    d[de]++;
    for(int i=at[cur];i;i=nex[i])
        if(to[i]!=fa)
            dfs(to[i],cur,de+1); 
}
void init(){
    n=read();
    int u,v;
    for(int i=1;i<n;i++){
        u=read(),v=read();
        to[++cnt]=v,nex[cnt]=at[u],at[u]=cnt;
        to[++cnt]=u,nex[cnt]=at[v],at[v]=cnt;
    } 
}
void solve(){
    for(int i=1;i<=n;i++){
        memset(f,0,sizeof(f));
        memset(g,0,sizeof(g));
        for(int j=at[i];j;j=nex[j]){
            dfs(to[j],i,1);
            for(int k=1;k<=n;k++)//合并集合
                ans+=d[k]*g[k],g[k]+=d[k]*f[k],f[k]+=d[k],d[k]=0;
        }
    }
    printf("%lld\n",ans);
}
int main(){
    init();
    solve();
    return 0;
}

Powered By Valine
v1.5.2