#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
const int N=1e5;
typedef tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
vector<pair<int,int>> e[N+10];
bool vis[N+10];
int siz[N+10];
int dep[N+10];
int par[N+10];
int mx[N+10];
ordered_set os;
ordered_set st[N+10];
priority_queue<pair<int,int>> pq;
void dfs_size(int x,int p)
{
siz[x]=1;
for(auto v:e[x])
{
if(v.fi!=p && !vis[v.fi])
{
dfs_size(v.fi,x);
siz[x]+=siz[v.fi];
}
}
return;
}
int find_centro(int x,int p,int size_all)
{
for(auto v:e[x])
{
if(v.fi!=p && !vis[v.fi])
{
int tmp=find_centro(v.fi,x,size_all);
if(tmp!=-1)
return tmp;
}
}
if(2*siz[x]>=size_all)
return x;
return -1;
}
long long centro(int x,int k)
{
dfs_size(x,0);
x=find_centro(x,0,siz[x]);
vis[x]=true;
dep[x]=0;
mx[x]=0;
os.clear();
while(!pq.empty())
pq.pop();
os.insert({0,x});
for(auto [v,c]:e[x])
{
if(!vis[v])
{
dep[v]=1;
mx[v]=c;
par[v]=v;
st[v].clear();
pq.emplace(-mx[v],v);
}
}
long long ans=0;
while(!pq.empty())
{
int y=pq.top().se;
pq.pop();
int d=mx[y]-dep[y]-k;
ans+=os.order_of_key({d+1,0})-st[par[y]].order_of_key({d+1,0});
os.insert({dep[y],y});
st[par[y]].insert({dep[y],y});
for(auto [v,c]:e[y])
{
if(!vis[v] && siz[v]<siz[y])
{
mx[v]=max(mx[y],c);
dep[v]=dep[y]+1;
par[v]=par[y];
pq.emplace(-mx[v],v);
}
}
}
for(auto [v,c]:e[x])
{
if(!vis[v])
ans+=centro(v,k);
}
return ans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,k;
cin>>n>>k;
for(int i=1;i<n;i++)
{
int a,b,c;
cin>>a>>b>>c;
e[a].emplace_back(b,c);
e[b].emplace_back(a,c);
}
cout<<2*centro(1,k)<<"\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
11980 KB |
Output is correct |
| 2 |
Correct |
12 ms |
12196 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
12072 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
12036 KB |
Output is correct |
| 2 |
Correct |
10 ms |
12064 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
12096 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
11980 KB |
Output is correct |
| 2 |
Correct |
12 ms |
12196 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
12072 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
