P4220 通道笔记

边分治神题。

前置知识：边分治，虚树。

题意

给定 $3$ 棵有边权的树，每棵树都含有 $n$ 个节点，令 $dis_i(x, y)$ 表示 $(x, y)$ 在第 $i$ 棵树上的距离。求一组 $(i, j)$，使得 $\sum\limits_{k = 1}^3 dis_k(i, j)$ 最大，为了方便，只需输出最大值。

题解

考虑边分治。下面用 $T_i$ 来表示第 $i$ 棵树。

对 $T_1$ 进行边分治，设 $d_1(x)$ 表示 $x$ 点到分治边一侧的距离，那么答案就转化成了 $d_1(i) + d_1(j) + dis_2(i, j) + dis_3(i, j)$。然后将当前分治块内的所有点在 $T_2$ 上拉出来，建一棵虚树 $T'_2$，再设 $d_2(x)$ 表示 $x$ 在 $T_2$ 上的带权深度，答案又转化成了 $d_1(i) + d_1(j) + d_2(i) + d_2(j) + dis_3(i, j) - 2d_2{p}$，其中 $p$ 表示 $T'_2$ 中 $(i, j)$ 的 $\text{LCA}$，显然 $p$ 也是 $T_2$ 中 $(i, j)$ 的 $\text{LCA}$。

所以现在枚举 $p$，然后在 $p$ 在 $T'_2$ 的子树中，找到 $(i, j)$ 使：1. $i, j$ 在 $T_1$ 的分治边的两侧。2. 答案最大。接着可以发现，上面的答案可以变成 $(d_1 + d_2)(i) + (d_1 + d_2)(j) + dis_3(i, j) - 2d_2(p)$，因为 $p$ 是我们枚举的，故可以省略。接着，考虑把 $(d_1 + d_2)(i) + (d_1 + d_2)(j)$ 给转化一下。一个精妙的处理方法是：在 $T_3$ 中新建 $i', j'$，然后将 $i'$ 与 $i$ 之间连一条边权为 $d_1(i) + d_2(i)$ 的边，对 $j$ 和 $j'$ 同理。这样答案就转化成了 $dis_3(i', j') - 2d_2(p)$，也就是求 $T_3$ 中的最长路（要保证 $i, j$ 在分治边的两侧）。

我们发现，最长路竟然是可以合并的！也就是说：设 $x$ 只有两个儿子，$l, r$ 是 $x$ 的左儿子子树的最长路两端点，$l', r'$ 是右儿子的。那么 $x$ 的最长路两端点一定是 $l, l', r, r'$ 中的两个！根据这个结论，就可以在 $T'_2$ 上面进行合并了。有一个细节，设 $L$ 表示分治边左侧的点集，$R$ 表示分治边右侧的点集，如果要保证 $(i, j)$ 在分治边的两侧，那么先把 $L$ 的最长路和 $R$ 的最长路分别求出，然后再对两个最长路，分别选出一个点进行合并，这才能保证 $i, j$ 在不同侧的限制。

于是这题就做完了，时间复杂度 $O(n \log^2 n)$。

---

代码有点难写，调了 1.5h。。。感叹代码能力的弱小。代码最下面的“类人群星闪耀时”是我的弱智sb错误。

代码：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 2E5 + 5;
int n; i64 d[3][N], sd[N], ans; bool L[N], R[N];
vector <pair <int, i64>> G[4][N];
struct t3 {
  int yf[N][20], S = 19, dep[N]; i64 dd[N], bq[N];
  void dfs(int x, int fa) {
    for (auto [v, w] : G[3][x]) {
      if (v == fa) continue;
      dd[v] = dd[x] + w; yf[v][0] = x;
      dep[v] = dep[x] + 1;
      for (int i = 1; i <= S; ++i) yf[v][i] = yf[yf[v][i - 1]][i - 1];
      dfs(v, x);
    }
  }
  int glca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = S; i >= 0; --i) if (dep[u] - (1 << i) >= dep[v])
      u = yf[u][i];
    if (u == v) return u;
    for (int i = S; i >= 0; --i) if (yf[u][i] != yf[v][i])
      u = yf[u][i], v = yf[v][i];
    return yf[u][0];
  }
  void nd(int x, i64 val) {bq[x] = val;}
  i64 dis(int u, int v) {
    if (!u || !v) return -1E9;
    if (u == v) return 0;
    return dd[u] + dd[v] - 2 * dd[glca(u, v)] + bq[u] + bq[v];
  }
} pd;
struct virt {
  int h[N], m, len, a[N << 1], ll, dfn[N], S = 19, yf[N][20], dep[N], ccnt; 
  void push(int x) {h[++len] = x;} vector <int> E[N];
  void conn(int x, int y) {E[x].emplace_back(y); E[y].emplace_back(x);}
  void dfs(int x, int fa) {
    dfn[x]  = ++ccnt;
    for (auto [v, w] : G[2][x]) {
      if (v == fa) continue;
      d[2][v] = d[2][x] + w;
      dep[v] = dep[x] + 1; yf[v][0] = x;
      for (int i = 1; i <= S; ++i) yf[v][i] = yf[yf[v][i - 1]][i - 1];
      dfs(v, x);
    }
  }
  int glca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = S; ~i; --i) if (dep[u] - (1 << i) >= dep[v])
      u = yf[u][i];
    if (u == v) return u;
    for (int i = S; ~i; --i) 
      if (yf[u][i] != yf[v][i]) {
        u = yf[u][i], v = yf[v][i];
      }
    return yf[u][0];
  }
  void build() {
    sort(h + 1, h + len + 1, [&](int x, int y) {return dfn[x] < dfn[y];});
    for (int i = 1; i <= len; ++i) a[++ll] = h[i];
    for (int i = 1; i < len; ++i) {
      a[++ll] = glca(h[i], h[i + 1]);
    } a[++ll] = 1;
    sort(a + 1, a + 1 + ll, [&](int x, int y) {return dfn[x] < dfn[y];});
    ll = unique(a + 1, a + 1 + ll) - a - 1;
    for (int i = 1; i < ll; ++i) {
      int lc = glca(a[i], a[i + 1]);
      conn(lc, a[i + 1]);
    }
  }
  void init() {
    dep[1] = 1; for (int i = 0; i <= S; ++i) yf[1][i] = 1; 
    dfs(1, 0);
    pd.dep[1] = 1; for (int i = 0; i <= S; ++i)
      pd.yf[1][i] = 1;
    pd.dfs(1, 0);
  }
  struct cl {
    int p, q; i64 Di;
    i64 val() {return Di;}
    bool operator < (const cl &w) const {return Di < w.Di;}
    cl (int x, int y) {p = x; q = y; Di = pd.dis(p, q);}
    cl () {p = q = 0; Di = -1E9; }
  } ;
  cl merge(cl a, cl b) {
    return max({cl(a.p, a.q), cl(a.p, b.q), cl(a.p, b.p), cl(a.q, b.p), cl(a.q, b.q), cl(b.p, b.q)});
  }
  cl lmg(cl a, cl b) {
    return max({cl(a.p, b.p), cl(a.p, b.q), cl(a.q, b.p), cl(a.q, b.q)});
  }
  pair <cl, cl> dp(int x, int fa) {
    cl l, r;
    if (L[x]) l = cl(x, x);
    else if (R[x]) r = cl(x, x);
    for (auto v : E[x]) {
      if (v == fa) continue;
      auto [tl, tr] = dp(v, x);
      ans = max(ans, lmg(l, tr).val() - 2 * d[2][x]);
      ans = max(ans, lmg(r, tl).val() - 2 * d[2][x]); 
      l = merge(l, tl);
      r = merge(r, tr);
    } 
    return make_pair(l, r);
  }
  void solve() {
    build();
    for (int i = 1; i <= len; ++i) if (L[h[i]] || R[h[i]]) 
      pd.nd(h[i], d[1][h[i]] + d[2][h[i]]);
    dp(1, 0);
  }
  void clear() {
    for (int i = 1; i <= ll; ++i)
      E[a[i]].clear();
    len = ll = 0;
  }
} vi;
struct bfz {
  int sz[N], root, dmx, dsum, head[N], nex[N << 1], tot = 1, m; bool vis[N];
  struct E {int to, nxt; i64 dis;} edge[N << 1];
  void add(int x, int y, i64 z) {
    edge[++tot] = (E) {x, y, z};
    nex[tot] = head[x]; head[x] = tot;
  }
  void getroot(int x, int fa) {
    sz[x] = 1;
    for (int i = head[x]; i; i = nex[i]) {
      int v = edge[i].nxt;
      if (v == fa || vis[i >> 1]) continue;
      getroot(v, x); sz[x] += sz[v];
      int tmp = max(sz[v], dsum - sz[v]);
      if (dmx > tmp) {
        dmx = tmp;
        root = i;
      }
    }
  }
  void rebuild(int x, int fa) {
    int tmp = 0, len = G[1][x].size(), last;
    for (auto [v, w] : G[1][x]) {
      if (v == fa) continue;
      ++tmp; if (tmp == 1) {
        add(v, x, w); add(x, v, w);
        last = x;
      } else if (tmp == len - (x != 1)) {
        add(last, v, w); add(v, last, w);
      } else {
        ++m;
        add(last, m, 0); add(m, last, 0);
        last = m;
        add(m, v, w); add(v, m, w);
      }
    }
    for (auto [v, w] : G[1][x]) if (v != fa)
      rebuild(v, x);
  }
  void dfs(int x, int fa, bool typ) {
    if (x <= n) vi.push(x);
    if (!typ) L[x] = 1;
    else R[x] = 1;
    for (int i = head[x]; i; i = nex[i]) {
      int v = edge[i].nxt; i64 w = edge[i].dis;
      if (v == fa || vis[i >> 1]) continue;
      d[1][v] = d[1][x] + w;
      dfs(v, x, typ);
    }
  }
  void clear(int x, int fa) {
    L[x] = R[x] = 0;
    for (int i = head[x]; i; i = nex[i]) {
      int v = edge[i].nxt;
      if (v == fa || vis[i >> 1]) continue;
      clear(v, x);
    }
  }
  int cnt = 0;
  void solve(int x, int nsum) {
    root = 0; dmx = 1E9; dsum = nsum;
    getroot(x, 0); if (!root) return ;
    vis[root >> 1] = 1;
    int u = edge[root].to, v = edge[root].nxt;
    i64 w = edge[root].dis;
    d[1][u] = 0; dfs(u, v, 0); d[1][v] = w; dfs(v, u, 1);
    vi.solve(); vi.clear(); 
    clear(u, v); clear(v, u);
    solve(u, dsum - sz[v]);
    solve(v, sz[v]);
  }
  void solve() {
    m = n;
    rebuild(1, 0);
    solve(1, m);
  }
} b;
signed main(void) {
  ios :: sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin >> n;
  for (int i = 1; i <= 3; ++i) {
    for (int j = 1; j < n; ++j) {
      int u, v; i64 w; cin >> u >> v >> w;
      G[i][u].emplace_back(v, w);
      G[i][v].emplace_back(u, w);
    }
  } vi.init(); 
  b.solve(); 
  cout << ans << '\n';
  return 0;
}
/*
类人群星闪耀时：
1. E 未清空。
2. 虚树中加入了三度化的虚点。
3. 更新答案时，没注意 a∈L,b∈R 的条件。
4. d[1][x] 忘记清空。
5. 十年OI一场空，______________。
*/