Description

给你一棵TREE,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于K

Input

N（n<=40000） 接下来n-1行边描述管道，按照题目中写的输入 接下来是k

Output

一行，有多少对点之间的距离小于等于k

Sample Input

7

1 6 13

6 3 9

3 5 7

4 1 3

2 4 20

4 7 2

10

Sample Output

5

 

又是一道点分治的题，方法同聪聪可可。

1 #include
      
        2 #include
       
         3 using namespace std; 4 const int N=40010; 5 int deep[N],head[N],son[N],f[N],d[N],root,ans,n,sum,cnt,k; 6 bool vis[N]; 7 struct ee{
    int to,next,w;}e[N*2]; 8 void insert(int u,int v,int w){ 9     e[++cnt].to=v;e[cnt].next=head[u];e[cnt].w=w;head[u]=cnt;10 }11  12 void getroot(int x,int fa){13     son[x]=1;f[x]=0;14     for (int i=head[x];i;i=e[i].next){15         int v=e[i].to;16         if (vis[v]||v==fa) continue;17         getroot(v,x);18         son[x]+=son[v];19         f[x]=max(f[x],son[v]);20     }21     f[x]=max(f[x],sum-f[x]);22     if (f[x]