/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|     16|int main() {
   20|     16|  rd rd;
   21|     16|  wt wt;
   22|     16|  int n = rd.uh();
   23|     16|#ifdef LOCAL
   24|     16|  std::memset(head, 0, 4 * n);
   25|     16|#endif
   26|  3.61M|  for (int i = 1; i < n; ++i) {
                                       ^3.61M
  ------------------
  |  Branch (26:19): [True: 100.00%, False: 0.00%]
  ------------------
   27|  3.61M|    int a = rd.uh();
   28|  3.61M|    int b = rd.uh();
   29|  3.61M|    int c = rd.uw();
   30|  3.61M|    edge[i * 2 | 0] = {b, c, head[a]}, head[a] = i * 2 | 0;
   31|  3.61M|    edge[i * 2 | 1] = {a, c, head[b]}, head[b] = i * 2 | 1;
   32|  3.61M|  }
   33|     16|  std::pair<u64, int> ans;
   34|     32|  let bfs = [&](int u) {
                ^16
   35|     32|    pa[u] = -1;
   36|     32|    queue[0] = {0, u};
   37|     32|    ans = {};
   38|  7.22M|    for (int i = 0, j = 0; i < n; ++i) {
                                                ^7.22M
  ------------------
  |  Branch (38:28): [True: 100.00%, False: 0.00%]
  ------------------
   39|  7.22M|      let[d, u] = queue[i];
   40|  21.6M|      for (int e = head[u]; e; e = edge[e].nxt) {
                                             ^14.4M
  ------------------
  |  Branch (40:29): [True: 66.67%, False: 33.33%]
  ------------------
   41|  14.4M|        int v = edge[e].to;
   42|  14.4M|        int len = edge[e].len;
   43|  14.4M|        if (v != pa[u]) {
  ------------------
  |  Branch (43:13): [True: 50.00%, False: 50.00%]
  ------------------
   44|  7.22M|          pa[v] = u;
   45|  7.22M|          ans = std::max(ans, queue[++j] = {d + len, v});
   46|  7.22M|        }
   47|  14.4M|      }
   48|  7.22M|    }
   49|     32|  };
   50|     16|  bfs(0);
   51|     16|  int u = ans.second;
   52|     16|  bfs(u);
   53|     16|  int v = ans.second;
   54|     16|  u64 d = ans.first;
   55|     16|  wt.ud(d);
   56|     16|  int c = 0;
   57|   500k|  for (int i = v; i != -1; i = pa[i]) ++c;
                                         ^500k      ^500k
  ------------------
  |  Branch (57:19): [True: 100.00%, False: 0.00%]
  ------------------
   58|     16|  wt.uw(c);
   59|   500k|  for (int i = v; i != -1; i = pa[i]) wt.uw(i);
                                         ^500k      ^500k
  ------------------
  |  Branch (59:19): [True: 100.00%, False: 0.00%]
  ------------------
   60|     16|  return 0;
   61|     16|}