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