pgbattle_2020_katsuobushi_D.cpp

#include <bits/stdc++.h>
#include <variant>
#include <atcoder/all>
#define FOR(i,k,n) for(ll i=(k);i<(ll)(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(x) begin(x),end(x)
 
using namespace std;
using namespace std::string_literals;
using namespace atcoder;
using ll = int64_t;
using vecint = vector<int>;
using vecll = vector<ll>;

struct Edge {
  ll src,dest,weight;
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;

void add_edge(Graph& g, ll src, ll dest, ll weight) {
  g[src].push_back({src, dest, weight});
  g[dest].push_back({dest, src, weight});
}

int dfs(const Graph& g, vecll& cent, int i, int p = -1) {
  int cnt = 1;
  int mxch = 0;
  for (auto&&e:g[i]) {
    if (e.dest == p) continue;
    int ch = dfs(g, cent, e.dest, i);
    mxch = max(mxch, ch);
    cnt += ch;
  }
  int n = size(g);
  if (mxch <= n / 2 && n - cnt <= n / 2) {
    cent.push_back(i);
  }
  return cnt;
}

void dist(const Graph& g, vecll& d, ll current, int i, int p) {
  d.push_back(current);
  for (auto&&e:g[i]) {
    if (e.dest == p) continue;
    dist(g, d, current + e.weight, e.dest, i);
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  ll n;
  cin>>n;
  Graph g(n);
  REP(i,n-1) {
    ll a,b,m;
    cin>>a>>b>>m;
    --a;--b;
    add_edge(g, a, b, m);
  }
  vecll cent;
  dfs(g, cent, 0);
  if(size(cent) != 2) {
    cout<<"0\n";
    return 0;
  }
  vector<vecll> d(2);
  REP(i,2) {
    dist(g, d[i], 0, cent[i], cent[1-i]);
    sort(ALL(d[i]));
  }
  ll cent_edge_len = -1;
  for(auto&&e:g[cent.front()]) {
    if (e.dest != cent.back()) continue;
    cent_edge_len = e.weight;
    break;
  }
  ll ans = 0;
  REP(i,2) {
    auto& dp = d[i];
    auto& dq = d[1-i];
    for(auto&&d1:dp) {
      auto first = upper_bound(ALL(dq), d1-cent_edge_len);
      auto last = upper_bound(ALL(dq), d1+cent_edge_len);
      //cerr<<i<<" "<<d1;
      //for(auto itr=first;itr!=last;++itr) cerr<<" "<<*itr;
      //cerr<<endl;
      ans += last - first;
    }
  }
  cout<<ans<<"\n";
  return 0;
}