[POI2014]HOT-Hotels

摘要

题意:一颗无根树,每条边长度相同。选 3 个点两两距离相等,有多少种方案? .

不难证明三条路径交汇于一个中心点。以这个中心点为根的话,那么这三个结点深度相同。于是我们枚举根结点,并统计每一个深度的结点数(注意,这三个点要分布在不同的根结点下的一级子树中),然后统计一下即可.

统计的关键过程是,对于 统计

考虑我们已经完成了 的统计,那么对于 就会累加

于是维护一下前缀和和平方和即可,总复杂度 .

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e3+5;
int n,ans,c[N];
vector<int> a[N];

struct qxx{int nex,t;};
qxx e[N*2];
int h[N],cnt=1;
void add_path(int f,int t){e[++cnt]=(qxx){h[f],t},h[f]=cnt;}

void calc(int u,int p,int dep,int* a){++a[dep];
    for(int i=h[u];i;i=e[i].nex)if(e[i].t!=p)calc(e[i].t,u,dep+1,a);
}
signed main(){scanf("%lld",&n);
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%lld%lld",&u,&v);
        add_path(u,v),add_path(v,u);
    }
    for(int u=1;u<=n;u++){// 以 u 为中心点
        for(int i=1;a[i].size();i++)a[i].clear();
        for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t;
            memset(c,0,sizeof(c));
            calc(v,u,1,c);//v 的深度为 1, 结果记录在 c 中
            for(int i=1;c[i];i++)a[i].push_back(c[i]);
        }
        for(int i=1;a[i].size();i++){if(a[i].size()<3)continue;// 没有贡献
            int s=a[i][0]+a[i][1],s2=a[i][0]*a[i][0]+a[i][1]*a[i][1];
            for(int j=2;j<a[i].size();j++){ans+=a[i][j]*(s*s-s2)/2;
                s+=a[i][j],s2+=a[i][j]*a[i][j];
            }
        }
    }
    printf("%lld",ans);
    return 0;
}

extra: 加强版用长链剖分做???


  转载请注明: Sshwy's Blog [POI2014]HOT-Hotels

 上一篇
[LuoguP1251] 餐巾计划问题 [LuoguP1251] 餐巾计划问题
摘要 复习一下网络流 一个餐厅在相继的 天里,每天需用一些餐巾。第 天需要 块餐巾 。餐厅可以购买新的餐巾, 每块餐巾的费用为 ;或者把旧餐巾送到快洗部,洗一块需
2019.04.06
下一篇 
[POI2014]KUR-Couriers [POI2014]KUR-Couriers
摘要 给一个数列,每次询问一个区间内有没有一个数出现次数严格超过一半. . 复习一下主席树~ 区间 对应版本 的权值线段树的差。每次查询当前结点的左右儿子结点的大小
2019.04.05
  目录