CodeForces161D： Distance in Tree（树分治）

A tree is a connected graph that doesn't contain any cycles.

The distance between two vertices of a tree is the length (in edges) of the shortest path between these vertices.

You are given a tree with n vertices and a positive number k. Find the number of distinct pairs of the vertices which have a distance of exactly k between them. Note that pairs (v, u) and (u, v) are considered to be the same pair.

Input

The first line contains two integers n and k (1 ≤ n ≤ 50000, 1 ≤ k ≤ 500) — the number of vertices and the required distance between the vertices.

Next n - 1 lines describe the edges as "a_i b_i" (without the quotes) (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i), where a_i and b_i are the vertices connected by the i-th edge. All given edges are different.

Output

Print a single integer — the number of distinct pairs of the tree's vertices which have a distance of exactly k between them.

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Examples

Input

Output

Input

Output

题意：给定一棵树，问树上有多少个点对距离是K（K<=500）。

思路：明显的基础分治题，分别累计经过根节点的距离为K的点对。说他基础是以为既不需要排序，也不需要去重。复杂度O（NlogN*K）

（感悟：分治=若干个小分治+线性解决当前层 =NlogN。

分治=若干个小分治+logN解决当前层 =NlogN*logN。

分治=若干个小分治+K*线性解决当前层 =N*K*logN。

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

int Laxt[maxn],Next[maxn],To[maxn];

int sz[maxn],son[maxn],root,cnt,N,K,ans,sn; //sn，小树的大小。

int num[],tnum[],vis[maxn];

void read(int &x){

    x=;     char c=getchar();

    while(c>''||c<'') c=getchar();

    while(c>=''&&c<='') x=(x<<)+(x<<)+c-'',c=getchar();

}

void add(int u,int v)

{

    Next[++cnt]=Laxt[u];

    Laxt[u]=cnt; To[cnt]=v;

}

void getroot(int u,int fa)

{

    sz[u]=; son[u]=;

    for(int i=Laxt[u];i;i=Next[i]){

        int v=To[i];

        if(v==fa||vis[v]) continue;

        getroot(v,u); sz[u]+=sz[v];

        son[u]=max(son[u],sz[v]);

    }

    son[u]=max(sz[u],sn-son[u]);

    if(root==||son[root]>son[u]) root=u;

}

void getdep(int u,int fa,int dis)

{

    if(K>=dis) ans+=num[K-dis],tnum[dis]++;

    if(K==dis)  return ;

    for(int i=Laxt[u];i;i=Next[i])

      if(To[i]!=fa&&!vis[To[i]])

        getdep(To[i],u,dis+);

}

void dfs(int u)

{

    vis[u]=;

    for(int i=;i<=K;i++) num[i]=; num[]=;

    for(int i=Laxt[u];i;i=Next[i]){         //暴力部分

        if(vis[To[i]]) continue;

        for(int j=;j<=K;j++) tnum[j]=;

        getdep(To[i],,);

        for(int j=;j<=K;j++) num[j]+=tnum[j];

    }

    for(int i=Laxt[u];i;i=Next[i]){      //以大化小，分治部分

        if(vis[To[i]]) continue;

        sn=sz[To[i]]; root=;

        getroot(To[i],u); dfs(root);

    }

}

int main()

{

    int u,v; scanf("%d%d",&N,&K);

    for(int i=;i<N;i++){

        read(u) ; read(v) ;

        add(u,v); add(v,u);

    }

    root=; sn=N; getroot(,); dfs(root);

    printf("%d\n",ans);

    return ;

}

巴特西

CodeForces161D： Distance in Tree（树分治）

最新文章

热门文章