点分治

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<queue>
#include<vector>
#include<algorithm>
#include<cmath>
#include<stack>
#include<map>
using namespace std;
#define R register
#define ll long long
#define fo(i,a,b) for(R int (i)=(a);(i)<=(b);++(i))
#define dbg(x) cout<<#x<<"="<<x<<'\n'
#define mmt(x,y) memset(x,y,sizeof(x))
#define maxn 20000
int n,k,m,fasiz[maxn],siz[maxn],d[maxn],dep[maxn],sum,rt,ans;
int head[maxn],to[maxn<<1],nxt[maxn<<1],v[maxn<<1],tot=1;
bool vis[maxn];
void add(int x,int y,int vv)
{
nxt[++tot]=head[x];
head[x]=tot;to[tot]=y;v[tot]=vv;
}
void getroot(int x,int faa)
{
siz[x]=1;fasiz[x]=0;
for(int i=head[x];i;i=nxt[i])
if(to[i]!=faa&&!vis[to[i]])
{
getroot(to[i],x);
siz[x]+=siz[to[i]];
fasiz[x]=max(fasiz[x],siz[to[i]]);
}
fasiz[x]=max(fasiz[x],sum-siz[x]);
if(fasiz[x]<fasiz[rt])rt=x;
}
void getdep(int x,int faa)
{
dep[++dep[0]]=d[x];
for(int i=head[x];i;i=nxt[i])
if(to[i]!=faa&&!vis[to[i]])
{
d[to[i]]=d[x]+v[i];
getdep(to[i],x);
}
}
int cal(int x,int cost)
{
d[x]=cost;dep[0]=0;
getdep(x,0);
sort(dep+1,dep+dep[0]+1);
R int l=1,r=dep[0],sum=0;
while(l<r)
{
if(dep[l]+dep[r]<=k)sum+=r-l,l++;
else r--;
}
return sum;
}

void solve(int x)
{
ans+=cal(x,0);
vis[x]=1;
for(int i=head[x];i;i=nxt[i])
if(!vis[to[i]])
{
ans-=cal(to[i],v[i]);
sum=siz[to[i]];
rt=0;
getroot(to[i],0);
solve(rt);
}
}
int main()
{
while(scanf("%d%d",&n,&k),n&&k)
{
ans=rt=m=0;tot=1;
mmt(vis,0);mmt(head,0);
fo(i,2,n)
{
R int x,y,vv;scanf("%d%d%d",&x,&y,&vv);
add(x,y,vv);add(y,x,vv);
}
fasiz[0]=1e9;sum=n;
getroot(1,0);solve(rt);
printf("%d\n",ans);
}
return 0;
}
显示 Gitment 评论