| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1208951 | MasterDebater | Race (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+5;
int n,k,ai,bi,ci,mxd,par[N],sz[N],len[N];
ll ans;
vector<int>v[N];
bool bio[N];
int precompute(int node,int parent){
sz[node]=1;
for(int i=0;i<(int)v[node].size();i++)if(!bio[v[node][i]] and v[node][i]!=parent)sz[node]+=precompute(v[node][i],node);
return sz[node];
}
void solve(int node,int parent,int depth,bool b){
if(depth>k)return;
mxd=max(mxd,depth);
if(b)len[depth]++;
else ans+=len[k-depth];
for(int i=0;i<(int)v[node].size();i++){
if(v[node][i]!=parent and !bio[v[node][i]])
solve(v[node][i],node,depth+1,b);
}
return;
}
int FindCentroid(int node,int parent,int vel){
for(int i=0;i<(int)v[node].size();i++)if(v[node][i]!=parent and !bio[v[node][i]])
if(sz[v[node][i]]>vel/2)return FindCentroid(v[node][i],node,vel);
return node;
}
void CentroidDecompostition(int node){
precompute(node,-1);
int centroid=FindCentroid(node,-1,sz[node]);
mxd=0;
len[0]=1;
for(int i=0;i<(int)v[centroid].size();i++)if(!bio[v[centroid][i]]){
solve(v[centroid][i],centroid,1,0);
solve(v[centroid][i],centroid,1,1);
}
for(int i=0;i<=mxd;i++)len[i]=0;
node=centroid;
bio[node]=1;
for(int i=0;i<(int)v[node].size();i++) {
int child=v[node][i];
if (bio[child])continue;
CentroidDecompostition(child);
}
return;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>k;
for(int i=0;i<n;i++)par[i]=-1;
for(int i=1;i<n;i++){
cin>>ai>>bi>>ci,ai--,bi--;
v[ai].push_back(bi);
v[bi].push_back(ai);
}
CentroidDecompostition(0);
cout<<ans<<'\n';
return 0;
}