51nod 1353 樹

題目

題解

這裡證明一下複雜度

1.數學證法

S u S_u Su​表示 u u u的子樹大小

這裡隻考慮大小的級别，常數就不考慮了

T = ∑ u ∑ f a i = u , f a j = u S i S j T=\sum_u\sum_{fa_i=u,fa_j=u}S_iS_j T=∑u​∑fai​=u,faj​=u​Si​Sj​

= ∑ u [ ( ∑ f a i = u S i ) 2 − ∑ f a i = u S i 2 ] =\sum_u[(\sum_{fa_i=u}S_i)^2-\sum_{fa_i=u}S_i^2] =∑u​[(∑fai​=u​Si​)2−∑fai​=u​Si2​]

= ∑ u S u 2 − ∑ u ∑ f a i = u S i 2 =\sum_uS_u^2-\sum_u\sum_{fa_i=u}S_i^2 =∑u​Su2​−∑u​∑fai​=u​Si2​

考慮到每個點隻有一個父親，是以：

∑ u ∑ f a i = u S i 2 = ∑ S i 2 \sum_u\sum_{fa_i=u}S_i^2=\sum S_i^2 ∑u​∑fai​=u​Si2​=∑Si2​

T = O ( n 2 ) T=O(n^2) T=O(n2)

2.理論證法

這個算法看作枚舉每個點，統計以它作為 l c a lca lca的點對個數，然後這些值全加起來

本質上就是求點對的個數，而點對個數是 O ( n 2 ) O(n^2) O(n2)的，是以這個算法複雜度也是 O ( n 2 ) O(n^2) O(n2)的

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=1e9+7,N=2002;
struct node{
	int to,ne;
}e[N<<1];
int tot,h[N],f[N][N],s[N],i,n,k,x,y;
void add(int x,int y){
	e[++tot]=(node){y,h[x]};
	h[x]=tot;
}
void dfs(int u,int fa){
	f[u][s[u]=1]=1;
	for (int t=h[u],v;t;t=e[t].ne)
		if ((v=e[t].to)!=fa){
			dfs(v,u);
			for (int i=s[u];i;i--){
				for (int j=s[v];j;j--) (f[u][i+j]+=(ll)f[u][i]*f[v][j]%M)%=M;
				f[u][i]=(ll)f[u][i]*f[v][0]%M;
			}
			s[u]+=s[v];
		}
	for (int i=k;i<=s[u];i++) (f[u][0]+=f[u][i])%=M;
}
int main(){
	scanf("%d%d",&n,&k);
	for (i=1;i<n;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x);
	dfs(1,0);
	printf("%d",f[1][0]);
}