题面:
Tree
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.
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.
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
题意:
给你一棵TREE,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于K
输入格式: 每次输入n,k(如果n0&&k0停止),接着n-1行,每行3个数描述边
这道题就是一道淀粉质点分治的模板题，具体不多讲，如果不会看看这个吧
接下来直接上代码
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=200001;
int read() {
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9')c=='-'?f=-1,c=getchar():c=getchar();
while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x*f;
}
int n,k;
int dep[N];/*从当前节点i到枚举当前树的根节点父亲的距离*/
int f[N];/*当i为根节点时最大字数大小*/
int vis[N];/*i节点是否被当根使用过*/
int siz[N];/*以i节点为根时,其子树(包括本身)的节点个数*/
int root;/*根节点*/
struct node {
int next,to,v;
} a[N<<1];
int head[N],cnt,sum/*这棵当前递归的这棵树的大小*/;
void add(int x,int y,int c) {
a[++cnt].to=y;
a[cnt].next=head[x];
a[cnt].v=c;
head[x]=cnt;
}
void findroot(int k,int fa) {
f[k]=0,siz[k]=1;
for(int i=head[k]; i; i=a[i].next) {
int v=a[i].to;
if(vis[v]||v==fa)
continue;
findroot(v,k);
siz[k]+=siz[v];
f[k]=max(f[k],siz[v]);
}
f[k]=max(f[k],sum-siz[k]);
if(f[k]<f[root])
root=k;
}
int tot;
void finddep(int k,int fa,int l) {
dep[++tot]=l;
for(int i=head[k]; i; i=a[i].next) {
int v=a[i].to;
if(v==fa||vis[v])
continue;
finddep(v,k,l+a[i].v);
}
}
int K;
int calc(int k,int L) {
tot=0;
finddep(k,0,L);
sort(dep+1,dep+1+tot);
int l=1,r=tot,ans=0;
while(l<r){
if(dep[l]+dep[r]<=K)
l++,ans+=r-l+1;
else
r--;
}
return ans;
}
int js;
void devide(int k) {
vis[k]=1;
js+=calc(k,0);
for(int i=head[k]; i; i=a[i].next) {
int v=a[i].to;
if(vis[v])
continue;
js-=calc(v,a[i].v);
root=0,sum=siz[v];
findroot(v,0);
devide(root);
}
}
int main() {
int n=read(),x,y,z;
K=read();
while(n&&K){
memset(head,0,sizeof(head)),cnt=0;//head
memset(vis,0,sizeof(vis));//标记数组
for (int i=1; i<n; i++)
x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);
sum=f[0]=n,js=0;//总数
findroot(1,0);
devide(root);
printf("%d
",js);
n=read(),K=read();
}
return 0;
}
注意初始化!!!注意初始化!!!注意初始化!!!
重要的事情说三遍