#include <bits/stdc++.h>
using namespace std;
#define MAX 100002
int n;
int x;
struct st{
int go;
long long int cost;
st(int go_,long long int cost_){
go = go_;
cost = cost_;
}
};
vector<st> v[MAX];
bool used[MAX];
long long int ans = 0;
long long int way = 0;
vector<long long int> vv;
int cnt[MAX];
inline void dfs(int b,long long int c,int pr=-1){
cnt[b] = 1;
if(c<=x)vv.push_back(c);
for (int i = 0; i < v[b].size(); i++){
if (v[b][i].go == pr)continue;
if (used[v[b][i].go]){
continue;
}
dfs(v[b][i].go,c+v[b][i].cost,b);
cnt[b] += cnt[v[b][i].go];
}
}
vector<vector<long long int> > V;
vector<pair<long long int, int> > lis;
vector<vector<int> > ids;
vector<long long int> bit;
vector<int> cnt_bit;
void add(int i, long long int x){
int MX = bit.size();
i++;
while (i < MX){
bit[i] += x;
if(x>0)cnt_bit[i] += 1;
else cnt_bit[i] -= 1;
i += i&-i;
}
}
long long int sum(int i){
long long int r = 0;
i++;
while (i){
r += bit[i];
i -= i&-i;
}
return r;
}
int sum_cnt(int i){
int r = 0;
i++;
while (i){
r += cnt_bit[i];
i -= i&-i;
}
return r;
}
pair<int, int> find_cent(int b,int all,int pr=-1){
pair<int, int> r = make_pair(INT_MAX, -1);
int M = 0;
int sub = 0;
for (int i = 0; i < v[b].size(); i++){
if (used[v[b][i].go] || pr == v[b][i].go)continue;
r = min(r, find_cent(v[b][i].go, all, b));
M = max(M, cnt[v[b][i].go]);
sub += cnt[v[b][i].go];
}
M = max(M, all - sub-1);
r = min(r, make_pair(M, b));
return r;
}
void solve(int b){
used[b] = true;
V.clear();
for (int i = 0; i < v[b].size(); i++){
if (!used[v[b][i].go]){
dfs(v[b][i].go, v[b][i].cost);
way += vv.size();
V.push_back(vv);
vv.clear();
}
}
if (V.size() == 0)return;
lis.clear();
ids.clear();
ids.assign(V.size(), vector<int>());
for (int i = 0; i < V.size(); i++){
for (int j = 0; j < V[i].size(); j++){
ans += V[i][j];
lis.push_back(make_pair(V[i][j],i));
}
}
bit.assign(lis.size()+1, 0);
cnt_bit.assign(lis.size() + 1, 0);
sort(lis.begin(), lis.end());
for (int i = 0; i < lis.size(); i++){
ids[lis[i].second].push_back(i);
add(i, lis[i].first);
}
for (int i = 0; i < ids.size(); i++){
for (int j = 0; j < ids[i].size(); j++){
add(ids[i][j], -lis[ids[i][j]].first);
}
for (int j = 0; j < V[i].size(); j++){
long long int eq = x - V[i][j];
int ii = upper_bound(lis.begin(), lis.end(), make_pair(eq,INT_MAX)) - lis.begin();
int way2 = sum_cnt(ii-1);
ans += sum(ii-1);
ans += (long long int)(way2)*(long long int)(V[i][j]);
way += way2;
}
}
for (int i = 0; i < v[b].size(); i++){
if (used[v[b][i].go] == false){
solve(find_cent(v[b][i].go, cnt[v[b][i].go]).second);
}
}
}
bool cmp(st &a, st &b){
return a.cost < b.cost;
}
set<pair<int, int> > mp;
int main(){
cin >> n >> x;
for (int i = 1; i < n; i++){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
a--;
b--;
v[a].push_back(st(b, c));
v[b].push_back(st(a, c));
}
solve(0);
memset(used, false, sizeof(used));
for (int i = 0; i < n; i++){
sort(v[i].begin(), v[i].end(), cmp);
}
for (int i = 0; i < n; i++){
for (int j = 0; j < v[i].size(); j++){
if (v[i][j].cost>x){
if (mp.count(make_pair(i,v[i][j].go))==0){
mp.insert(make_pair(i, v[i][j].go));
mp.insert(make_pair(v[i][j].go, i));
int go = v[i][j].go;
long long int min_cost = INT_MAX;
for (int kk = 0; kk < min(3,(int)v[go].size()); kk++){
if (v[go][kk].go != i){
min_cost = min(min_cost, v[go][kk].cost);
}
}
if (j != 0){
min_cost = min(min_cost, v[i][0].cost);
}
else{
if (v[i].size() > 1){
min_cost = min(min_cost, v[i][1].cost);
}
}
if (min_cost != INT_MAX){
min_cost += x;
}
long long int C = v[i][j].cost;
C = min(C, min_cost);
if (n>v[i].size()+v[go].size()){
C = min(C, x * 2LL);
}
way++;
ans += C;
}
}
}
}
long long int P = (n);
P *= (n - 1);
P /= 2LL;
P -= way;
P *= x;
ans += P;
printf("%lld\n", ans);
return 0;
}
./Main.cpp: In function ‘int main()’:
./Main.cpp:149:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &a, &b, &c);
^