/tmp/solutions/build/tree_diameter-main.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|       |
   16|   926k|def tree_diameter(int u, int p) -> std::pair<u64, int> {
   17|   926k|  pa[u] = p;
   18|   926k|  std::pair<u64, int> ans{0, u};
   19|  2.77M|  for (int e = head[u]; e; e = edge[e].nxt) {
                                         ^1.85M
  ------------------
  |  Branch (19:25): [True: 66.67%, False: 33.33%]
  ------------------
   20|  1.85M|    int v = edge[e].to;
   21|  1.85M|    int len = edge[e].len;
   22|  1.85M|    if (v != p) {
  ------------------
  |  Branch (22:9): [True: 50.00%, False: 50.00%]
  ------------------
   23|   926k|      def res = tree_diameter(v, u);
   24|   926k|      res.first += len;
   25|   926k|      ans = std::max(ans, res);
   26|   926k|    }
   27|  1.85M|  }
   28|   926k|  return ans;
   29|   926k|}
   30|       |
   31|       |} // namespace
   32|       |
   33|      1|int main() {
   34|      1|  rd rd;
   35|      1|  wt wt;
   36|      1|  int n = rd.uh();
   37|      1|#ifdef LOCAL
   38|      1|  std::memset(head, 0, 4 * n);
   39|      1|#endif
   40|   463k|  for (int i = 1; i < n; ++i) {
                                       ^463k
  ------------------
  |  Branch (40:19): [True: 100.00%, False: 0.00%]
  ------------------
   41|   463k|    int a = rd.uh();
   42|   463k|    int b = rd.uh();
   43|   463k|    int c = rd.uw();
   44|   463k|    edge[i * 2 | 0] = {b, c, head[a]}, head[a] = i * 2 | 0;
   45|   463k|    edge[i * 2 | 1] = {a, c, head[b]}, head[b] = i * 2 | 1;
   46|   463k|  }
   47|      1|  let[_, u] = tree_diameter(0, -1);
   48|      1|  let[d, v] = tree_diameter(u, -1);
   49|      1|  int c = 0;
   50|     58|  for (int i = v; i != -1; i = pa[i]) ++c;
                                         ^57        ^57
  ------------------
  |  Branch (50:19): [True: 98.28%, False: 1.72%]
  ------------------
   51|      1|  wt.ud(d);
   52|      1|  wt.uw(c);
   53|     58|  for (int i = v; i != -1; i = pa[i]) wt.uw(i);
                                         ^57        ^57
  ------------------
  |  Branch (53:19): [True: 98.28%, False: 1.72%]
  ------------------
   54|      1|  return 0;
   55|      1|}