#include <bits/stdc++.h>
#define pii pair <int,int>
#define F first
#define S second
#define all(a) a.begin(),a.end()
#define pb push_back
#define ll long long
using namespace std ;
const int maxn = 5e5 +10 , inf = 1e9 ;
int mark[maxn] , t[maxn] , c[maxn] , s =0 , n , k ;
vector <int> to[maxn] ;vector <pii> G[maxn] ;
vector <int> fen[maxn] ;
vector <pair <pii , int> > vec;
int maxh = 0 , cnt = 1 , sz ;
void find(int v , int p){
t[v] = 1;
bool ok = 0 ;
for(int i = 0 ; i < G[v].size() ; i++){
int u = G[v][i].S , w = G[v][i].F ;
if(u == p || mark[u] == 1)continue ;
find(u , v) ;
t[v] += t[u] ;
if(t[u] > sz/2){
ok = 1 ;
}
}
if((sz-t[v]) > sz/2)ok = 1;
if(ok == 0)s = v ;
}
void bui(int v , int p , int dis , int mx , int jd){
vec.pb({{mx , dis} , v});
c[v] = jd ;
while(to[jd].size() <= (dis+1))to[jd].pb(0) ,fen[jd].pb(0) ;
to[jd][dis]++;
maxh = max(maxh , dis) ;
for(int i =0 ; i < G[v].size(); i++){
int w = G[v][i].F , u = G[v][i].S ;
if(u == p || mark[u] == 1)continue ;
bui(u , v , dis+1 , max(mx , w) , jd) ;
}
}
void upd(int x , int y , int val){
y++;
while(y < ((int)fen[x].size())){
fen[x][y] += val ;
y += (y&-y) ;
}
}
int que(int x, int y){
y++;
int ans =0 ;
y = min(y , (int)fen[x].size() - 1) ;
while(y>0){
ans += fen[x][y] ;
y -= (y&-y) ;
}
return ans ;
}
int yep(int x , int p){
int t =1 ;
for(int i = 0 ; i <G[x].size() ; i++){
int u = G[x][i].S ;
if(p == u || mark[u] == 1)continue ;
t += yep(u , x) ;
}
return t ;
}
ll ans =0 ;
void sen(int v){
maxh = 0 ;s = -1 ;
find(v , 0) ;maxh++;
mark[s] = 1;
c[s] = -1 ;
vec.clear();
for(int i = 0 ; i < G[s].size() ; i++){
int u = G[s][i].S ;
to[i].clear() ;
fen[i].clear();
if(mark[u] == 1)continue ;
bui(u , s , 1 , G[s][i].F , i);
fen[i].pb(0);
for(int j = 0 ; j < to[i].size() ; j++){
upd(i , j , to[i][j]) ;
}
}
fen[(int)G[s].size()].clear();
fen[(int)G[s].size()].pb(0) ;
for(int i =0 ; i <= vec.size() ; i++){
fen[(int)G[s].size()].pb(0) ;
}
for(int i =0 ;i < vec.size() ; i++){
upd((int)G[s].size() , vec[i].F.S , 1 );
}
upd((int)G[s].size() , 0 , 1) ;
sort(all(vec));reverse(all(vec)) ;
for(int i = 0 ; i < vec.size() ; i++){
ans = (ans + que((int)G[s].size() , vec[i].F.F - vec[i].F.S - k) - que(c[vec[i].S] , vec[i].F.F - vec[i].F.S - k));
upd((int)G[s].size() , vec[i].F.S , -1);
upd(c[vec[i].S] , vec[i].F.S , -1) ;
}
int ls = s;
for(int i =0 ; i < G[ls].size() ; i++){
int u = G[ls][i].S ;
if(mark[u] == 1)continue ;
sz = yep(u ,ls) ;
sen(u ) ;
}
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0) ;
cin >> n >> k ;
for(int i = 1 ; i < n; i++){
int v, u , w ;
cin >> v >> u>> w ;
G[v].pb({w , u}) ;
G[u].pb({w , v}) ;
}
sz = n ;
sen(1) ;
cout << ans * 2 << "\n" ;
}
/*
3 1
1 2 3
1 3 2
4 1
1 2 1
2 3 2
3 4 3
*/
Compilation message
Main.cpp: In function 'void find(int, int)':
Main.cpp:20:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for(int i = 0 ; i < G[v].size() ; i++){
| ~~^~~~~~~~~~~~~
Main.cpp:21:29: warning: unused variable 'w' [-Wunused-variable]
21 | int u = G[v][i].S , w = G[v][i].F ;
| ^
Main.cpp: In function 'void bui(int, int, int, int, int)':
Main.cpp:35:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
35 | while(to[jd].size() <= (dis+1))to[jd].pb(0) ,fen[jd].pb(0) ;
| ~~~~~~~~~~~~~~^~~~~~~~~~
Main.cpp:38:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for(int i =0 ; i < G[v].size(); i++){
| ~~^~~~~~~~~~~~~
Main.cpp: In function 'int yep(int, int)':
Main.cpp:64:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for(int i = 0 ; i <G[x].size() ; i++){
| ~~^~~~~~~~~~~~
Main.cpp: In function 'void sen(int)':
Main.cpp:78:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int i = 0 ; i < G[s].size() ; i++){
| ~~^~~~~~~~~~~~~
Main.cpp:85:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for(int j = 0 ; j < to[i].size() ; j++){
| ~~^~~~~~~~~~~~~~
Main.cpp:92:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for(int i =0 ; i <= vec.size() ; i++){
| ~~^~~~~~~~~~~~~
Main.cpp:95:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for(int i =0 ;i < vec.size() ; i++){
| ~~^~~~~~~~~~~~
Main.cpp:101:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for(int i = 0 ; i < vec.size() ; i++){
| ~~^~~~~~~~~~~~
Main.cpp:107:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for(int i =0 ; i < G[ls].size() ; i++){
| ~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
35512 KB |
Output is correct |
2 |
Correct |
20 ms |
35540 KB |
Output is correct |
3 |
Correct |
28 ms |
35556 KB |
Output is correct |
4 |
Correct |
19 ms |
35684 KB |
Output is correct |
5 |
Correct |
19 ms |
35672 KB |
Output is correct |
6 |
Correct |
19 ms |
35696 KB |
Output is correct |
7 |
Correct |
19 ms |
35616 KB |
Output is correct |
8 |
Correct |
18 ms |
35712 KB |
Output is correct |
9 |
Correct |
19 ms |
35668 KB |
Output is correct |
10 |
Correct |
20 ms |
35568 KB |
Output is correct |
11 |
Correct |
18 ms |
35556 KB |
Output is correct |
12 |
Correct |
18 ms |
35572 KB |
Output is correct |
13 |
Correct |
18 ms |
35568 KB |
Output is correct |
14 |
Correct |
18 ms |
35540 KB |
Output is correct |
15 |
Correct |
18 ms |
35540 KB |
Output is correct |
16 |
Correct |
18 ms |
35560 KB |
Output is correct |
17 |
Correct |
18 ms |
35580 KB |
Output is correct |
18 |
Correct |
18 ms |
35588 KB |
Output is correct |
19 |
Correct |
17 ms |
35540 KB |
Output is correct |
20 |
Correct |
17 ms |
35568 KB |
Output is correct |
21 |
Correct |
18 ms |
35644 KB |
Output is correct |
22 |
Correct |
18 ms |
35540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
35540 KB |
Output is correct |
2 |
Correct |
16 ms |
35540 KB |
Output is correct |
3 |
Correct |
16 ms |
35504 KB |
Output is correct |
4 |
Correct |
17 ms |
35668 KB |
Output is correct |
5 |
Correct |
30 ms |
37232 KB |
Output is correct |
6 |
Correct |
108 ms |
44052 KB |
Output is correct |
7 |
Correct |
211 ms |
52000 KB |
Output is correct |
8 |
Correct |
238 ms |
52608 KB |
Output is correct |
9 |
Correct |
226 ms |
52116 KB |
Output is correct |
10 |
Correct |
231 ms |
52412 KB |
Output is correct |
11 |
Correct |
217 ms |
52024 KB |
Output is correct |
12 |
Correct |
227 ms |
52504 KB |
Output is correct |
13 |
Correct |
225 ms |
52028 KB |
Output is correct |
14 |
Correct |
238 ms |
52452 KB |
Output is correct |
15 |
Correct |
233 ms |
52304 KB |
Output is correct |
16 |
Correct |
211 ms |
52404 KB |
Output is correct |
17 |
Correct |
218 ms |
52496 KB |
Output is correct |
18 |
Correct |
214 ms |
52296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
35512 KB |
Output is correct |
2 |
Correct |
20 ms |
35540 KB |
Output is correct |
3 |
Correct |
28 ms |
35556 KB |
Output is correct |
4 |
Correct |
19 ms |
35684 KB |
Output is correct |
5 |
Correct |
19 ms |
35672 KB |
Output is correct |
6 |
Correct |
19 ms |
35696 KB |
Output is correct |
7 |
Correct |
19 ms |
35616 KB |
Output is correct |
8 |
Correct |
18 ms |
35712 KB |
Output is correct |
9 |
Correct |
19 ms |
35668 KB |
Output is correct |
10 |
Correct |
20 ms |
35568 KB |
Output is correct |
11 |
Correct |
18 ms |
35556 KB |
Output is correct |
12 |
Correct |
18 ms |
35572 KB |
Output is correct |
13 |
Correct |
18 ms |
35568 KB |
Output is correct |
14 |
Correct |
18 ms |
35540 KB |
Output is correct |
15 |
Correct |
18 ms |
35540 KB |
Output is correct |
16 |
Correct |
18 ms |
35560 KB |
Output is correct |
17 |
Correct |
18 ms |
35580 KB |
Output is correct |
18 |
Correct |
18 ms |
35588 KB |
Output is correct |
19 |
Correct |
17 ms |
35540 KB |
Output is correct |
20 |
Correct |
17 ms |
35568 KB |
Output is correct |
21 |
Correct |
18 ms |
35644 KB |
Output is correct |
22 |
Correct |
18 ms |
35540 KB |
Output is correct |
23 |
Correct |
16 ms |
35540 KB |
Output is correct |
24 |
Correct |
16 ms |
35540 KB |
Output is correct |
25 |
Correct |
16 ms |
35504 KB |
Output is correct |
26 |
Correct |
17 ms |
35668 KB |
Output is correct |
27 |
Correct |
30 ms |
37232 KB |
Output is correct |
28 |
Correct |
108 ms |
44052 KB |
Output is correct |
29 |
Correct |
211 ms |
52000 KB |
Output is correct |
30 |
Correct |
238 ms |
52608 KB |
Output is correct |
31 |
Correct |
226 ms |
52116 KB |
Output is correct |
32 |
Correct |
231 ms |
52412 KB |
Output is correct |
33 |
Correct |
217 ms |
52024 KB |
Output is correct |
34 |
Correct |
227 ms |
52504 KB |
Output is correct |
35 |
Correct |
225 ms |
52028 KB |
Output is correct |
36 |
Correct |
238 ms |
52452 KB |
Output is correct |
37 |
Correct |
233 ms |
52304 KB |
Output is correct |
38 |
Correct |
211 ms |
52404 KB |
Output is correct |
39 |
Correct |
218 ms |
52496 KB |
Output is correct |
40 |
Correct |
214 ms |
52296 KB |
Output is correct |
41 |
Correct |
17 ms |
35540 KB |
Output is correct |
42 |
Correct |
213 ms |
51964 KB |
Output is correct |
43 |
Correct |
233 ms |
52500 KB |
Output is correct |
44 |
Correct |
218 ms |
52160 KB |
Output is correct |
45 |
Correct |
238 ms |
52344 KB |
Output is correct |
46 |
Correct |
220 ms |
52056 KB |
Output is correct |
47 |
Correct |
228 ms |
52520 KB |
Output is correct |
48 |
Correct |
221 ms |
52048 KB |
Output is correct |
49 |
Correct |
237 ms |
52452 KB |
Output is correct |
50 |
Correct |
277 ms |
52240 KB |
Output is correct |
51 |
Correct |
217 ms |
52368 KB |
Output is correct |
52 |
Correct |
106 ms |
44376 KB |
Output is correct |
53 |
Correct |
102 ms |
44692 KB |
Output is correct |
54 |
Correct |
91 ms |
44192 KB |
Output is correct |
55 |
Correct |
105 ms |
44624 KB |
Output is correct |
56 |
Correct |
99 ms |
44640 KB |
Output is correct |
57 |
Correct |
231 ms |
44628 KB |
Output is correct |
58 |
Correct |
222 ms |
44508 KB |
Output is correct |
59 |
Correct |
223 ms |
44768 KB |
Output is correct |
60 |
Correct |
231 ms |
44632 KB |
Output is correct |
61 |
Correct |
213 ms |
44856 KB |
Output is correct |
62 |
Correct |
176 ms |
44120 KB |
Output is correct |
63 |
Correct |
194 ms |
44704 KB |
Output is correct |
64 |
Correct |
189 ms |
44652 KB |
Output is correct |
65 |
Correct |
24 ms |
36040 KB |
Output is correct |
66 |
Correct |
17 ms |
35528 KB |
Output is correct |