#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++;
// cout << v << " " << s << " " << sz << " st -------- \n" ;
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 ;
to[i].pb(0);
fen[i].pb(0);
bui(u , s , 1 , G[s][i].F , i);
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++){
// cout << vec[i].F.F << " " << vec[i].F.S << " " << vec[i].S << " -- "<< que((int)G[s].size() , vec[i].F.F - vec[i].F.S - k) << " " << vec[i].F.F - vec[i].F.S - k << " " << que(c[vec[i].S] , vec[i].F.F - vec[i].F.S - k) << "<-----\n" ;
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));
}
// cout << ans << "--" << endl ;
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:79: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]
79 | for(int i = 0 ; i < G[s].size() ; i++){
| ~~^~~~~~~~~~~~~
Main.cpp:87:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for(int j = 0 ; j < to[i].size() ; j++){
| ~~^~~~~~~~~~~~~~
Main.cpp:94: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]
94 | for(int i =0 ; i <= vec.size() ; i++){
| ~~^~~~~~~~~~~~~
Main.cpp:97: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]
97 | for(int i =0 ;i < vec.size() ; i++){
| ~~^~~~~~~~~~~~
Main.cpp:103: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]
103 | for(int i = 0 ; i < vec.size() ; i++){
| ~~^~~~~~~~~~~~
Main.cpp:109: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]
109 | for(int i =0 ; i < G[ls].size() ; i++){
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
35540 KB |
Output is correct |
| 2 |
Correct |
20 ms |
35556 KB |
Output is correct |
| 3 |
Incorrect |
15 ms |
35464 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
35568 KB |
Output is correct |
| 2 |
Correct |
15 ms |
35540 KB |
Output is correct |
| 3 |
Incorrect |
16 ms |
35540 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
35540 KB |
Output is correct |
| 2 |
Correct |
20 ms |
35556 KB |
Output is correct |
| 3 |
Incorrect |
15 ms |
35464 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
