题解 P3565 【[POI2014]HOT-Hotels】

· · 题解

题意

给你一棵树,求任选3个点使得两两树上距离相同的方案数

n\le 10^5

题解

设f[u][i]表示u子树里距离u为i的节点个数

画个图就是这样![这里写图片描述](https://cdn.luogu.com.cn/upload/image_hosting/zwwmtsu2.png) $\forall v\in son_u$可以得到 $$ans=\sum_u(\sum_i f[u][i]*g[v][i+1]+f[u][i-1]*g[v][i])+g[u][0]$$ 考虑怎么转移$($初值$f[u][0]=1) g[u][i]=\sum_vg[v][j+1]+f[u][i]*f[v][i-1] f[u][i]=\sum_vf[v][i-1]

第一个式子中的f[u][i]是遍历完v前面子树得到的dp值

($大概根据定义画个图应该就能理解了$)

设mx[u]表示dep[u子树里最深的点]-dep[u]+1

可以发现对于u的任意一个儿子v上面的转移复杂度都是是mx[v]

而如果u只有一个儿子v可以发现

f[u][i]=f[v][i-1] g[u][i]=g[v][i+1]

用指针表示就是

f[u]=f[v]-1 g[u]=g[v]+1

也就是说如果是链的话我们可以线性转移

所以考虑长链剖分,u的重儿子son[u]就是mx最大的节点

对于重儿子我们用上面的转移,其他轻儿子暴力转移

可以证明这样的复杂度是线性的

考虑每个点u转移的复杂度p(u)=\sum_vmx[v]-mx[son[u]]=\sum_vmx[v]-mx[u]+1

总复杂度就是\sum_up(u)=\sum_u\sum_vmx[v]-mx[u]+1=n

空间复杂度度就是O(\sum长链长度)=O(n),用指针分配内存就好了

#include<bits/stdc++.h>
#define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i)
#define go(u) for(register int i=fi[u],v=e[i].to;i;v=e[i=e[i].nx].to)
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
char ss[1<<17],*A=ss,*B=ss;
inline char gc(){return A==B&&(B=(A=ss)+fread(ss,1,1<<17,stdin),A==B)?-1:*A++;}
template<class T>inline void sd(T&x){
    char c;T y=1;while(c=gc(),(c<48||57<c)&&c!=-1)if(c==45)y=-1;x=c-48;
    while(c=gc(),47<c&&c<58)x=x*10+c-48;x*=y;
}
char sr[1<<21],z[20];int C=-1,Z;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
template<class T>inline void we(T x){
    if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
const int N=1e5+5;
typedef int arr[N];
typedef long long ll;
struct eg{int nx,to;}e[N<<1];
int n,df[N*5],*f[N],*idf=df+1;arr fi,fa,mx,son;ll ans,dg[N*5],*g[N],*idg=dg+1;
inline void add(int u,int v){static int ce=0;e[++ce]={fi[u],v},fi[u]=ce;}
void dfs(int u){
    go(u)if(v^fa[u]){
        fa[v]=u,dfs(v),cmax(mx[u],mx[v]);
        if(mx[v]>mx[son[u]])son[u]=v;
    }++mx[u];
}
inline void Give(int u){f[u]=idf,idf+=mx[u]+1,idg+=mx[u]+1,g[u]=idg,idg+=mx[u]+1;}
void dp(int u){
    if(son[u])f[son[u]]=f[u]+1,g[son[u]]=g[u]-1,dp(son[u]);
    f[u][0]=1,ans+=g[u][0];
    go(u)if(v^fa[u]&&v^son[u]){
        Give(v),dp(v);
        fd(j,mx[v],0)ans+=g[v][j]*f[u][j-1]+g[u][j+1]*f[v][j];  
        fp(j,0,mx[v])g[u][j]+=g[v][j+1]+.3,f[u][j]+=f[v][j-1];
    }
}
int main(){
    #ifndef ONLINE_JUDGE
        file("s");
    #endif
    sd(n);int u,v;
    fp(i,2,n)sd(u),sd(v),add(u,v),add(v,u);
    dfs(1);Give(1);dp(1);
    printf("%lld\n",ans);
return 0;
}