/tmp/solutions/build/tree_diameter-fast.cpp:
    1|       |#include <common.h>
    2|       |prelude;
    3|       |
    4|       |namespace {
    5|       |
    6|       |constexpr int N = 5e5;
    7|       |
    8|       |struct {
    9|       |  int to;
   10|       |  int len;
   11|       |  int nxt;
   12|       |} edge[N * 2];
   13|       |int pa[N];
   14|       |int head[N];
   15|       |std::pair<u64, int> queue[N];
   16|       |
   17|       |} // namespace
   18|       |
   19|      1|int main() {
   20|      1|  rd rd;
   21|      1|  wt wt;
   22|      1|  int n = rd.uh();
   23|      1|#ifdef LOCAL
   24|      1|  std::memset(head, 0, 4 * n);
   25|      1|#endif
   26|   500k|  for (int i = 1; i < n; ++i) {
                                       ^499k
  ------------------
  |  Branch (26:19): [True: 100.00%, False: 0.00%]
  ------------------
   27|   499k|    int a = rd.uh();
   28|   499k|    int b = rd.uh();
   29|   499k|    int c = rd.uw();
   30|   499k|    edge[i * 2 | 0] = {b, c, head[a]}, head[a] = i * 2 | 0;
   31|   499k|    edge[i * 2 | 1] = {a, c, head[b]}, head[b] = i * 2 | 1;
   32|   499k|  }
   33|      1|  std::pair<u64, int> ans;
   34|      2|  let bfs = [&](int u) {
                ^1
   35|      2|    pa[u] = -1;
   36|      2|    queue[0] = {0, u};
   37|      2|    ans = {};
   38|  1.00M|    for (int i = 0, j = 0; i < n; ++i) {
                                                ^1.00M
  ------------------
  |  Branch (38:28): [True: 100.00%, False: 0.00%]
  ------------------
   39|  1.00M|      let[d, u] = queue[i];
   40|  2.99M|      for (int e = head[u]; e; e = edge[e].nxt) {
                                             ^1.99M
  ------------------
  |  Branch (40:29): [True: 66.67%, False: 33.33%]
  ------------------
   41|  1.99M|        int v = edge[e].to;
   42|  1.99M|        int len = edge[e].len;
   43|  1.99M|        if (v != pa[u]) {
  ------------------
  |  Branch (43:13): [True: 50.00%, False: 50.00%]
  ------------------
   44|   999k|          pa[v] = u;
   45|   999k|          ans = std::max(ans, queue[++j] = {d + len, v});
   46|   999k|        }
   47|  1.99M|      }
   48|  1.00M|    }
   49|      2|  };
   50|      1|  bfs(0);
   51|      1|  int u = ans.second;
   52|      1|  bfs(u);
   53|      1|  int v = ans.second;
   54|      1|  u64 d = ans.first;
   55|      1|  wt.ud(d);
   56|      1|  int c = 0;
   57|     51|  for (int i = v; i != -1; i = pa[i]) ++c;
                                         ^50        ^50
  ------------------
  |  Branch (57:19): [True: 98.04%, False: 1.96%]
  ------------------
   58|      1|  wt.uw(c);
   59|     51|  for (int i = v; i != -1; i = pa[i]) wt.uw(i);
                                         ^50        ^50
  ------------------
  |  Branch (59:19): [True: 98.04%, False: 1.96%]
  ------------------
   60|      1|  return 0;
   61|      1|}