Codeforces 161.D. Distance in Tree-树分治(点分治，不容斥版)-树上距离为K的点对数量-蜜汁TLE (VK Cup 2012 Round 1)

D. Distance in Tree

time limit per test

3 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

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 "ai bi" (without the quotes) (1 ≤ ai, bi ≤ n, ai ≠ bi), where ai and bi 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

Copy

output

Copy

input

Copy

output

Copy

Note

In the first sample the pairs of vertexes at distance 2 from each other are (1, 3), (1, 5), (3, 5) and (2, 4).

这道题就是求树上距离为K的点对数量。以前写过<=K的点对数量，直接<=K的数量 - <K的数量，讲道理应该也是可以的，但是一直TLE11和TLE17样例。。。

最后换了一种写法，直接求，没有中间-子树的过程，最后过了，有点迷。。。

不容斥版的快，就这样。

代码:

 //树分治-点分治

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 //#pragma GCC optimize(2)

 //#define FI(n) FastIO::read(n)

 const int inf=1e9+;

 const int maxn=1e5+;

 const int maxm=+;

 int head[maxn<<],tot;

 int root,allnode,n,m,k;

 bool vis[maxn];

 int deep[maxn],dis[maxn],siz[maxn],maxv[maxn];//deep[0]子节点个数(路径长度)，maxv为重心节点

 int num[maxm],cnt[maxm];

 ll ans=;

 //namespace FastIO {//读入挂

 //    const int SIZE = 1 << 16;

 //    char buf[SIZE], obuf[SIZE], str[60];

 //    int bi = SIZE, bn = SIZE, opt;

 //    int read(char *s) {

 //        while (bn) {

 //            for (; bi < bn && buf[bi] <= ' '; bi++);

 //            if (bi < bn) break;

 //            bn = fread(buf, 1, SIZE, stdin);

 //            bi = 0;

 //        }

 //        int sn = 0;

 //        while (bn) {

 //            for (; bi < bn && buf[bi] > ' '; bi++) s[sn++] = buf[bi];

 //            if (bi < bn) break;

 //            bn = fread(buf, 1, SIZE, stdin);

 //            bi = 0;

 //        }

 //        s[sn] = 0;

 //        return sn;

 //    }

 //    bool read(int& x) {

 //        int n = read(str), bf;

 //

 //        if (!n) return 0;

 //        int i = 0; if (str[i] == '-') bf = -1, i++; else bf = 1;

 //        for (x = 0; i < n; i++) x = x * 10 + str[i] - '0';

 //        if (bf < 0) x = -x;

 //        return 1;

 //    }

 //};

 inline int read()

 {

     int x=;char ch=getchar();

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

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x;

 }

 struct node{

     int to,next,val;

 }edge[maxn<<];

 void add(int u,int v,int w)//前向星存图

 {

     edge[tot].to=v;

     edge[tot].next=head[u];

     edge[tot].val=w;

     head[u]=tot++;

 }

 void init()//初始化

 {

     memset(head,-,sizeof head);

     memset(vis,,sizeof vis);

     tot=;

 }

 void get_root(int u,int father)//重心

 {

     siz[u]=;maxv[u]=;

     for(int i=head[u];~i;i=edge[i].next){

         int v=edge[i].to;

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

         get_root(v,u);//递归得到子树大小

         siz[u]+=siz[v];

         maxv[u]=max(maxv[u],siz[v]);//更新u节点的maxv

     }

     maxv[u]=max(maxv[u],allnode-siz[u]);//保存节点size

     if(maxv[u]<maxv[root]) root=u;//更新当前子树的重心

 }

 void get_dis(int u,int father)//获取子树所有节点与根的距离

 {

     if(dis[u]>k) return ;

     ans+=num[k-dis[u]];

     cnt[dis[u]]++;//计数

     for(int i=head[u];~i;i=edge[i].next){

         int v=edge[i].to;

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

         int w=edge[i].val;

         dis[v]=dis[u]+w;

         get_dis(v,u);

     }

 }

 void cal(int u,int now)

 {

     for(int i=;i<=k;i++){//初始化，清空

         num[i]=;

     }

     num[]=;

     for(int i=head[u];~i;i=edge[i].next){

         int v=edge[i].to;

         if(vis[v]) continue;

         for(int j=;j<=k;j++){//初始化

             cnt[j]=;

         }

         dis[v]=now;

         get_dis(v,u);//跑路径

         for(int j=;j<=k;j++){

             num[j]+=cnt[j];//计数

         }

     }

 }

 void solve(int u)//分治处理

 {

     cal(u,);

     vis[u]=;

     for(int i=head[u];~i;i=edge[i].next){

         int v=edge[i].to;

         int w=edge[i].val;

         if(vis[v]) continue;

         allnode=siz[v];

         root=;

         get_root(v,u);

         solve(root);

     }

 }

 int main()

 {

 //    FI(n);FI(k);

     n=read();k=read();

     init();

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

         int u,v,w;w=;

 //        FI(u);FI(v);

         u=read();v=read();

         add(u,v,w);

         add(v,u,w);

     }

     root=;allnode=n;maxv[]=inf;

     get_root(,);

     solve(root);

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

     return ;

 }

巴特西

Codeforces 161.D. Distance in Tree-树分治(点分治，不容斥版)-树上距离为K的点对数量-蜜汁TLE (VK Cup 2012 Round 1)

最新文章

热门文章