Tree
| Time Limit: 1000MS | Memory Limit: 30000K | |
| Total Submissions: 14067 | Accepted: 4555 |
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
点分治。。。具体题解就不写了
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
struct data{int x,y,s,next;} e[N<<1];
int vis[N],deep[N],son[N],f[N],d[N],head[N];
int n,K,x,y,s,cnt,sum,root,ans;
int read(){
int x = 0,f = 1,c = getchar();
while (c<'0' || c>'9'){if (c=='-') f = -1;c = getchar();}
while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
return x*f;
}
void Insert(int x,int y,int s){
e[++cnt].x = x;e[cnt].y = y;e[cnt].s = s;
e[cnt].next = head[x];head[x] = cnt;
}
void getroot(int x,int fa){
son[x] = 1;f[x] = 0;
for (int i=head[x];i;i=e[i].next)
if (e[i].y!=fa && !vis[e[i].y]){
getroot(e[i].y,x);
son[x]+=son[e[i].y];
f[x] = max(f[x],son[e[i].y]);
}
f[x] = max(f[x],sum-son[x]);
if (f[x]<f[root]) root = x;
}
void getdeep(int x,int fa){
deep[++deep[0]] = d[x];
for (int i=head[x];i;i=e[i].next)
if (e[i].y!=fa && !vis[e[i].y]){
d[e[i].y] = d[x]+e[i].s;
getdeep(e[i].y,x);
}
}
int calc(int x,int now){
d[x] = now;deep[0] = 0;
getdeep(x,-1);
sort(deep+1,deep+1+deep[0]);
int res = 0;
for (int l=1,r=deep[0];l<r;){
if (deep[l]+deep[r]<=K) {res+=r-l;l++;}
else r--;
}
return res;
}
void work(int x){
ans+=calc(x,0);
vis[x] = 1;
for (int i=head[x];i;i=e[i].next){
if (vis[e[i].y]) continue;
ans-=calc(e[i].y,e[i].s);
sum = son[e[i].y];
root = 0;
getroot(e[i].y,-1);
work(root);
}
}
int main(){
while (~scanf("%d%d",&n,&K) && n+K){
ans = root = cnt = 0;
memset(head,0,sizeof(head));
memset(vis,0,sizeof(vis));
for (int i=1;i<n;i++){
x = read();y = read();s = read();
Insert(x,y,s);Insert(y,x,s);
}
sum = n;f[0] = 1e9;
getroot(1,-1);
work(root);
printf("%d\n",ans);
}
}
2020年2月24日 14:48
Sooner or later, you could have realized your home wants some freshening upwards. It could possibly be as basic as sweeping the floors, dusting the particular furniture or simply your home needs a major washing session. Nonetheless, you could have a active schedule and you also don’t hold the time or the vitality to maintain your home clear. Maybe you'll rather spend the period with your household or close friends. Whatever the truth may become, we will help. Our staff of specialist cleaners will help save an individual from hrs or days of accomplishing boring and also tedious family chores.