Tree
| Time Limit: 1000MS | Memory Limit: 30000K | |
| Total Submissions: 11570 | Accepted: 3626 |
Description
Give a tree with n vertices,each edge has a length(positive integer less than 1001).
Define dist(u,v)=The min distance between node u and v.
Give an integer k,for every pair (u,v) of vertices is called valid if and only if dist(u,v) not exceed k.
Write a program that will count how many pairs which are valid for a given tree.
Define dist(u,v)=The min distance between node u and v.
Give an integer k,for every pair (u,v) of vertices is called valid if and only if dist(u,v) not exceed k.
Write a program that will count how many pairs which are valid for a given tree.
Input
The input contains several test cases. The first line of each test case contains two integers n, k. (n<=10000) The following n-1 lines each contains three integers u,v,l, which means there is an edge between node u and v of length l.
The last test case is followed by two zeros.
The last test case is followed by two zeros.
Output
For each test case output the answer on a single line.
Sample Input
5 4
1 2 3
1 3 1
1 4 2
3 5 1
0 0
Sample Output
8
Source
我的点分治第一题~~~
树上的路径分为两类：
经过根结点。不经过根结点。
那么我们能够选择每个点为根，然后计算经过这个根结点的长度<=k的路径，再依照同样的方法计算他的全部子树中的路径条数，这样就能不重不漏。
怎样计算经过根结点且长度<=k的路径条数？
用全部的减去在同一棵子树中的就能够。
怎么计算全部的长度<=k的路径？
用dfs求出每一个点的深度，存在一个数组里。然后从小到大排个序。用两个指针扫：l=1,r=tot，在l添加的过程中满足dep[l]+dep[r]<=k的r指针是不增的，所以O(n)能够出解，再加上sort的O(nlogn)。这个操作的复杂度为O(nlogn)。
所以总的复杂度为O(递归层数*nlogn)。怎样让递归层数最少？
每次让重心(找重心【POJ 1655】)当根结点，递归层数是logn的。
于是总复杂度为O(nlog^2n)~
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#define M 10005
using namespace std;
struct edge
{
int y,ne,l;
}e[M*100];
int ans,all,h[M],f[M],done[M],s[M],dep[M],tot=0,size,n,k,root;
void Addedge(int x,int y,int l)
{
tot++;
e[tot].y=y;
e[tot].ne=h[x];
e[tot].l=l;
h[x]=tot;
}
void Getroot(int x,int fa)
{
f[x]=0;
s[x]=1;
for (int i=h[x];i;i=e[i].ne)
{
int y=e[i].y;
if (y==fa||done[y]) continue;
Getroot(y,x);
s[x]+=s[y];
f[x]=max(f[x],s[y]);
}
f[x]=max(f[x],size-s[x]);
if (f[x]<f[root]) root=x;
}
void Getdep(int x,int fa,int de)
{
dep[++all]=de;
s[x]=1;
for (int i=h[x];i;i=e[i].ne)
{
int y=e[i].y,l=e[i].l;
if (y==fa||done[y]) continue;
Getdep(y,x,de+l);
s[x]+=s[y];
}
}
int calc(int x,int de)
{
int an=0;
all=0;
Getdep(x,0,de);
sort(dep+1,dep+1+all);
for (int l=1,r=all;l<r;)
if (dep[l]+dep[r]<=k) an+=r-l++;
else r--;
return an;
}
void Solve(int x)
{
ans+=calc(x,0);
done[x]=true;
for (int i=h[x];i;i=e[i].ne)
{
int y=e[i].y;
if (done[y]) continue;
ans-=calc(y,e[i].l);
size=f[0]=s[y];
Getroot(y,root=0);
Solve(root);
}
}
int main()
{
while (scanf("%d%d",&n,&k)==2)
{
if (n==k&&n==0) break;
tot=0;
for (int i=1;i<=n;i++)
h[i]=0,done[i]=false;
for (int i=1;i<n;i++)
{
int x,y,l;
scanf("%d%d%d",&x,&y,&l);
Addedge(x,y,l);
Addedge(y,x,l);
}
ans=0;
f[0]=size=n;
Getroot(1,root=0);
Solve(root);
printf("%d\n",ans);
}
return 0;
}
感悟：
1.TLE是由于Solve(root)。写成Solve(y)了。。
2.点分治的关键是要知道路径分经过根结点和不经过根结点，由此找到递归方法。