#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
const int maxn = 2e5 + 5;
typedef pair<int, int> pii;
int n, k, pa[maxn], child[maxn], ans;
vector<pii> adj[maxn], g[maxn];
int bit[2*maxn];
bool check[maxn];
void update(int idx, int val){
for(++idx ; idx <= maxn-1 ; idx += idx&(-idx))
bit[idx] += val;
}
int get(int idx){
int res = 0;
for(++idx ; idx > 0 ; idx -= idx&(-idx))
res += bit[idx];
return res;
}
int dfs_sz(int u, int par){
child[u] = 1;
for(auto z : adj[u]){
auto [w, v] = z;
if(v == par || check[v])
continue;
child[u] += dfs_sz(v, u);
}
return child[u];
}
int centroid(int u, int par, int sz){
for(auto z : adj[u]){
auto [w, v] = z;
if(v == par || check[v])
continue;
if(child[v] >= sz / 2)
return centroid(v, u, sz);
}
return u;
}
void dfs_work(int u, int par, int val, int dist, int top){
g[top].push_back(make_pair(val, dist));
for(auto z : adj[u]){
auto [w, v] = z;
if(v == par || check[v])
continue;
dfs_work(v, u, max(val, w), dist+1, top);
}
}
void build(int u, int par){
int sz = dfs_sz(u, par);
int center = centroid(u, par, sz);
pa[center] = u;
vector<pii> vec = {};
for(auto z : adj[center]){
auto [w, v] = z;
if(check[v])
continue;
dfs_work(v, u, w, 1, v);
sort(g[v].begin(), g[v].end());
for(auto z : g[v]){
auto [val, dist] = z;
int cur = val - dist - k;
if(cur >= 0){
++ans;
ans -= get(cur);
}
update(dist, 1);
}
for(auto z : g[v]){
auto [val, dist] = z;
update(dist, -1);
vec.push_back(z);
}
}
sort(vec.begin(), vec.end());
for(auto z : vec){
auto [val, dist] = z;
int cur = val - dist - k;
if(cur >= 0){
ans += get(cur);
}
update(dist, 1);
}
for(auto z : vec){
auto [val, dist] = z;
update(dist, -1);
}
for(auto z : adj[center]){
auto [w, v] = z;
g[v].clear();
}
check[center] = true;
for(auto z : adj[center]){
auto [w, v] = z;
if(v == center || check[v])
continue;
build(v, center);
}
}
signed main(){
// freopen("love.inp" , "r" , stdin);
// freopen("love.out" , "w" , stdout);
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> k;
for(int i=1 ; i<n ; ++i){
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({w, v});
adj[v].push_back({w, u});
}
build(1, -1);
cout << ans * 2;
}
Compilation message
Main.cpp: In function 'long long int dfs_sz(long long int, long long int)':
Main.cpp:31:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
31 | auto [w, v] = z;
| ^
Main.cpp: In function 'long long int centroid(long long int, long long int, long long int)':
Main.cpp:41:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
41 | auto [w, v] = z;
| ^
Main.cpp: In function 'void dfs_work(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:53:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
53 | auto [w, v] = z;
| ^
Main.cpp: In function 'void build(long long int, long long int)':
Main.cpp:68:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
68 | auto [w, v] = z;
| ^
Main.cpp:75:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
75 | auto [val, dist] = z;
| ^
Main.cpp:85:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
85 | auto [val, dist] = z;
| ^
Main.cpp:93:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
93 | auto [val, dist] = z;
| ^
Main.cpp:102:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
102 | auto [val, dist] = z;
| ^
Main.cpp:107:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
107 | auto [w, v] = z;
| ^
Main.cpp:113:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
113 | auto [w, v] = z;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
12636 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12636 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
12636 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
12636 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
