#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
#define all(x) x.begin(), x.end()
const int N = 1e5+10;
int n, k, s[N], parent[N], rmq[N][22], r[N];
pair<int, int> arr[N];
ll ans = 0;
vector<pair<int, int>> g[N];
void dfs(int v, int p, int mx, int d){
for(auto u: g[v]){
if(u.first != p){
if(max(mx, u.second) - d - 1 >= k) ++ans;
dfs(u.first, v, max(mx, u.second), d+1);
}
}
}
int find_set(int v){
if(parent[v] == v) return v;
return parent[v] = find_set(parent[v]);
}
void union_set(int a, int b){
a = find_set(a);
b = find_set(b);
if(a != b){
if(s[a] < s[b]) swap(a, b);
parent[b] = a;
s[a] += s[b];
}
}
void precalc(){
for(int i = 1; i < n; i++) rmq[i][0] = r[i];
for(int j = 1; j < 22; j++){
for(int i = 1; i <= n; i++){
rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1<<j)][j - 1]);
}
}
}
int mx(int x, int y){
int k = __lg(y - x + 1);
return max(rmq[x][k], rmq[y - (1<<k) + 1][k]);
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
cin >> n >> k;
for(int i = 0; i < n-1; i++){
int a, b, w;
cin >> a >> b >> w;
arr[i + 1] = {w, i};
r[i + 1] = w;
g[a].pb({b, w});
g[b].pb({a, w});
}
precalc();
if(n <= 1000){
for(int i = 1; i <= n; i++) dfs(i, 0, 0, 0);
}else{
sort(arr + 1, arr + n);
for(int i = 1; i <= n; i++){
s[i] = 1;
parent[i] = i;
}
for(int i = 1; i < n; i++){
int pos = arr[i].second;
int x = s[find_set(pos)];
int y = s[find_set(pos+1)];
int t = mx(pos - x + 1, pos + 1 + y - 2) - k;
if(x <= t){
ans += ll(x) * ll(t - x + 1);
// ans +=
}
else{
ans += ll(min(t, y)) * ll((min(t, y) + 1) / 2);
}
union_set(i, i+1);
}
}
cout << ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
5196 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
5196 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
5196 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
