P3565 [POI2014]HOT-Hotels(n^2)

~~这个是n方做法，以后再补长链剖分的~~ 很明显到一个点距离相等的三个点两两之间距离相等。 所以我们枚举重心，对子树进行暴力统计,注意统计的顺序。 ``` #include<iostream> #include<cstdio> #include<algorithm> #include<string> #include<cstring> #include<cmath> using namespace std; typedef long long ll; const ll size=5e3+10; ll n,ans,tot,mx,d[size],tmp[size],s1[size],s2[size]; ll head[size],ver[size*2],next[size*2]; inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } inline void add(ll x,ll y){ ver[++tot]=y;next[tot]=head[x];head[x]=tot; } inline void dfs(ll x,ll fa){ mx=max(mx,d[x]); tmp[d[x]]++; for(ll i=head[x];i;i=next[i]){ ll y=ver[i]; if(y==fa) continue; d[y]=d[x]+1;dfs(y,x); } } int main(){ n=read(); for(ll i=1;i<n;i++){ ll x=read(),y=read(); add(x,y);add(y,x); } for(ll x=1;x<=n;x++){ memset(s1,0,sizeof(s1)); memset(s2,0,sizeof(s2)); for(ll i=head[x];i;i=next[i]){ ll y=ver[i];mx=0; d[y]=1;dfs(y,x); for(ll j=1;j<=mx;j++){ ans+=s2[j]*tmp[j]; s2[j]+=s1[j]*tmp[j]; s1[j]+=tmp[j]; } for(ll j=1;j<=mx;j++) tmp[j]=0; } } printf("%lld\n",ans); return 0; } ```