#include "race.h"
#include <bits/stdc++.h>
#define MAX 205000
typedef std::pair<int,int> pii;
int NA,KA;
std::vector<pii> con[MAX];
std::map<int,long long> mapa[MAX];
long long count=0;
void merge(int a,int b) {
if(mapa[a].size()<mapa[b].size())std::swap(mapa[a],mapa[b]);
for(auto&x:mapa[b]){
{
auto it = mapa[a].find(x.first+KA);
if(it!=mapa[a].end())count+=it->second;
}
{
auto it = mapa[a].find(x.first-KA);
if(it!=mapa[a].end())count+=it->second;
}
}
for(auto&x:mapa[b])mapa[a][x.first]+=x.second;
}
void dfs(int pos,int prev,int dist) {
mapa[pos][dist]++;
for(auto&x:con[pos]){
if(prev==x.first)continue;
dfs(x.first,pos,dist+x.second);
merge(pos,x.first);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
for(auto&x:mapa)x.clear();
for(auto&x:con)x.clear();
NA=N;KA=K;
for(int i=0;i!=N-1;++i){
int a,b,c;
a=H[i][0],b=H[i][1],c=L[i];
con[a].push_back({b,c});
con[b].push_back({a,c});
}
dfs(0,-1,0);
if(!count)count=-1;
return count;
}
