/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|     88|  for (int i = 1; i < n; ++i) {
                                       ^87
  ------------------
  |  Branch (26:19): [True: 98.86%, False: 1.14%]
  ------------------
   27|     87|    int a = rd.uh();
   28|     87|    int b = rd.uh();
   29|     87|    int c = rd.uw();
   30|     87|    edge[i * 2 | 0] = {b, c, head[a]}, head[a] = i * 2 | 0;
   31|     87|    edge[i * 2 | 1] = {a, c, head[b]}, head[b] = i * 2 | 1;
   32|     87|  }
   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|    178|    for (int i = 0, j = 0; i < n; ++i) {
                                                ^176
  ------------------
  |  Branch (38:28): [True: 98.88%, False: 1.12%]
  ------------------
   39|    176|      let[d, u] = queue[i];
   40|    524|      for (int e = head[u]; e; e = edge[e].nxt) {
                                             ^348
  ------------------
  |  Branch (40:29): [True: 66.41%, False: 33.59%]
  ------------------
   41|    348|        int v = edge[e].to;
   42|    348|        int len = edge[e].len;
   43|    348|        if (v != pa[u]) {
  ------------------
  |  Branch (43:13): [True: 50.00%, False: 50.00%]
  ------------------
   44|    174|          pa[v] = u;
   45|    174|          ans = std::max(ans, queue[++j] = {d + len, v});
   46|    174|        }
   47|    348|      }
   48|    176|    }
   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|     14|  for (int i = v; i != -1; i = pa[i]) ++c;
                                         ^13        ^13
  ------------------
  |  Branch (57:19): [True: 92.86%, False: 7.14%]
  ------------------
   58|      1|  wt.uw(c);
   59|     14|  for (int i = v; i != -1; i = pa[i]) wt.uw(i);
                                         ^13        ^13
  ------------------
  |  Branch (59:19): [True: 92.86%, False: 7.14%]
  ------------------
   60|      1|  return 0;
   61|      1|}