CF161D Distance in Tree

UPD:憨憨博客 公开处刑

LG传送门

长链剖分板子题。

长链剖分那么好写，跑得又快，为什么要写点分治呢？完了我现在看一道点分治题就想写长链剖分

如果还不会长链剖分请看我博客。

没什么好说的，时空复杂度\(O(n)\)直接洛谷rank1。

#include<cstdio>

#include<cctype>

#define R register

#define I inline

using namespace std;

const int S=50003,N=100003;

char buf[1000000],*p1,*p2;

I char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,S,stdin),p1==p2)?EOF:*p1++;}

I int rd(){

	R int f=0; R char c=gc();

	while(c<48||c>57) c=gc();

	while(c>47&&c<58) f=f*10+(c^48),c=gc();

	return f;

}

int h[S],s[N],g[N],p[S],q[S],d[S],t[S],*f[S],u[S],c,K,*e=u+1; long long o;

I int max(int x,int y){return x>y?x:y;}

I int min(int x,int y){return x<y?x:y;}

I void add(int x,int y){s[++c]=h[x],h[x]=c,g[c]=y;}

void dfs1(int x,int f){p[x]=f,d[x]=t[x]=d[f]+1;

	for(R int i=h[x],y;i;i=s[i])

		if((y=g[i])^f){dfs1(y,x);

			if(t[y]>t[x]) t[x]=t[y],q[x]=y;

		}

}

void dfs2(int x){f[x][0]=1;

	R int i,j,y,m,n=t[x]-d[x],k;

	if(q[x]) f[q[x]]=f[x]+1,dfs2(q[x]);

	for(i=h[x];i;i=s[i])

		if((y=g[i])^p[x]&&y^q[x]){f[y]=e,m=t[y]-d[y],e+=m+1,dfs2(y);

			for(j=max(K-n,0),k=min(m,K-1);j<=k;++j) o+=f[x][K-j]*f[y][j];

			for(j=0;j<=m;++j) f[x][j+1]+=f[y][j];

		}

	if(n>K) o+=f[x][K+1];

}

int main(){

	R int n=rd(),i,x,y;

	for(K=rd()-1,i=1;i<n;++i) x=rd(),y=rd(),add(x,y),add(y,x);

	dfs1(1,0),f[1]=e,e+=t[1],dfs2(1),printf("%lld",o);

	return 0;

}