Task

有两棵 $n$ 个点的树，称为树 A 和树 B。

有 $q$ 次询问，每次询问给出 $u, v$，求出：

$$ \max_{i = 1}^n \text{disA}_{u, i} + \text{disB}_{v, i} $$

$n \le 10^5, q \le 5 \times 10^5$。

Solution

好题。

维护树上路径最大值，很容易想到直径。但由于两棵树形态不同，这个思路行不行得通呢？

答案是肯定的。首先设树 A 的根为 $rt$。考虑对树 B 的每个点 $i$ 赋一个点权 $a_i = \text{disA}_{i, rt}$。

这样的话我们可以把询问离线，然后强制钦定树 A 的根节点为 $u$。如果询问 $u, v$，问题转化为了求 $\max a_i + \text{disB}_{v, i}$。

有一个经典结论：树上距离一个点最远的点一定是树的直径两端点之一。

有了这个结论，接下来我们就可以利用 Dynamic Diameter 的思想维护当前树的直径及其两端点、两端点的点权，从而求得答案。

那么显然树 A 的根是不断变化的，所以 $a_i$ 是不断变化的。这个可以通过换根，修改的话直接在欧拉序上区间修改即可。

具体时间复杂度取决于求 LCA 的算法：

• 如果使用预处理 $O(n)$，单次查询 $O(\log n)$ 的倍增 / 树剖，时间复杂度 $O(n \log n + q \log^2 n)$，可能会被卡常；

• 如果使用预处理 $O(n \log n)$，单次查询 $O(1)$ 的 ST 表，时间复杂度 $O((n + q) \log n)$，轻松通过（建议采用此写法）。

Code

#include <bits/stdc++.h>
#define _for(i, a, b)  for (int i = (a); i <= (b); i ++ )
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define P pair<int, int>
#define ll long long
using namespace std;
const int N = 1e5 + 5, M = 5e5 + 5;
int n, q; ll x, ans[M]; vector<P > qry[N];
namespace IO {
    static char buf[1000000], * p1 = buf, * p2 = buf, obuf[1000000], * p3 = obuf, cc[20];
    #define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, N - 5, stdin), p1 == p2) ? EOF : * p1 ++ )
    #define pc(x) (p3 - obuf < 1000000) ? ( * p3 ++ = x) : (fwrite(obuf, p3 - obuf, 1, stdout), p3 = obuf, * p3 ++ = x)
    inline int rd() {
        int val = 0, sgn = 1; char ch = gc();
        while (! isdigit(ch)) { if (ch == '-')  sgn = -1; ch = gc(); }
        while (isdigit(ch))  val = (val << 3) + (val << 1) + (ch ^ 48), ch = gc();
        return (val * sgn);
    }
    template <typename item>
    inline void print(item x){ 
        if (! x)  pc('0');
        int len = 0;
        if (x < 0)  x = - x, pc('-');
        while (x)  cc[len ++ ] = x % 10 | '0', x /= 10;
        while (len -- )  pc(cc[len]);
    }
    inline void write(long long x, char c) { print(x), pc(c); }
} using namespace IO;
struct Tree {
    int dfn_cnt, timer, sz[N], son[N], fa[N], dep[N], top[N], rk[N], dfn[N], pos[N], Log[N << 1], a[N << 1], ST[N << 1][20]; ll dis[N]; vector<P > G[N];
    inline void clear() {
        dfn_cnt = timer = 0;
        _for (i, 1, n)  dfn[i] = dis[i] = dep[i] = 0, G[i].clear();
    }
    void dfs1(int u) {
        sz[u] = 1, son[u] = - 1, a[pos[u] =  ++ timer] = u;
        for (P v : G[u])  if (v.F ^ fa[u]) {
            dep[v.F] = dep[u] + 1, dis[v.F] = dis[u] + v.S, fa[v.F] = u, dfs1(v.F), sz[u] += sz[v.F], a[ ++ timer] = u;
            if (son[u] == - 1 || sz[son[u]] < sz[v.F])  son[u] = v.F;
        }
    }
    void dfs2(int u, int Top) {
        top[u] = Top, rk[dfn[u] = ++ dfn_cnt] = u;
        if (son[u] == - 1)  return ;
        dfs2(son[u], Top);
        for (P v : G[u])  if (v.F ^ fa[u] && v.F ^ son[u])  dfs2(v.F, v.F);
    }
    inline int lca(int u, int v) {
        int U = top[u], V = top[v];
        while (U ^ V) {
            if (dep[U] >= dep[V])  u = fa[U];
            else  v = fa[V];
            U = top[u], V = top[v];
        }
        return (dep[u] < dep[v] ? u : v);
    }
    inline void pre_work() {
        Log[0] = - 1;
        _for (i, 1, n << 1)  Log[i] = Log[i >> 1] + 1;
        _for (i, 1, n << 1)  ST[i][0] = a[i];
        _for (j, 1, Log[n << 1])  _for (i, 1, (n << 1) - (1 << j) + 1)  ST[i][j] = dep[ST[i][j - 1]] < dep[ST[i + (1 << (j - 1))][j - 1]] ? ST[i][j - 1] : ST[i + (1 << (j - 1))][j - 1];
    }
    inline int query(int u, int v) {
        int l = pos[u], r = pos[v];
        if (l > r)  l ^= r ^= l ^= r;
        int k = Log[r - l + 1];
        return dep[ST[l][k]] < dep[ST[r - (1 << k) + 1][k]] ? ST[l][k] : ST[r - (1 << k) + 1][k];
    }
    inline ll dist(int u, int v) { return dis[u] + dis[v] - 2ll * dis[query(u, v)]; }
} T[2];
struct Seg_Tree {
    #define lc (p << 1)
    #define rc (p << 1 | 1)
    #define mid ((tr[p].l + tr[p].r) >> 1)
    struct Tree { int l, r, A, B; ll tag, dis, val_A, val_B; } res, tr[N << 2];
    inline int len(int p) { return tr[p].r - tr[p].l + 1; }
    inline bool In(int p, int l, int r) { return l <= tr[p].l && tr[p].r <= r; }
    inline void push_tag(int p, ll k) { tr[p].tag += k, tr[p].val_A += k, tr[p].val_B += k; }
    inline Tree merge(Tree u, Tree v) {
        res.l = u.l, res.r = v.r, res.dis = 0;
        if ((x = T[1].dist(u.A, u.B) + u.val_A + u.val_B) > res.dis)  res.dis = x, res.A = u.A, res.B = u.B, res.val_A = u.val_A, res.val_B = u.val_B;
        if ((x = T[1].dist(u.A, v.B) + u.val_A + v.val_B) > res.dis)  res.dis = x, res.A = u.A, res.B = v.B, res.val_A = u.val_A, res.val_B = v.val_B;
        if ((x = T[1].dist(v.A, u.B) + v.val_A + u.val_B) > res.dis)  res.dis = x, res.A = v.A, res.B = u.B, res.val_A = v.val_A, res.val_B = u.val_B;
        if ((x = T[1].dist(v.A, v.B) + v.val_A + v.val_B) > res.dis)  res.dis = x, res.A = v.A, res.B = v.B, res.val_A = v.val_A, res.val_B = v.val_B;
        if ((x = T[1].dist(u.A, v.A) + u.val_A + v.val_A) > res.dis)  res.dis = x, res.A = u.A, res.B = v.A, res.val_A = u.val_A, res.val_B = v.val_A;
        if ((x = T[1].dist(u.B, v.B) + u.val_B + v.val_B) > res.dis)  res.dis = x, res.A = u.B, res.B = v.B, res.val_A = u.val_B, res.val_B = v.val_B;
        return res;
    }
    inline void push_down(int p) { if (tr[p].tag)  push_tag(lc, tr[p].tag), push_tag(rc, tr[p].tag), tr[p].tag = 0; }
    void build(int p, int l, int r) {
        tr[p].l = l, tr[p].r = r, tr[p].tag = 0;
        if (l == r) { tr[p].A = tr[p].B = T[0].rk[l], tr[p].dis = 0, tr[p].val_A = tr[p].val_B = T[0].dis[T[0].rk[l]]; return ; }
        build(lc, l, mid), build(rc, mid + 1, r), tr[p] = merge(tr[lc], tr[rc]);
    }
    void update(int p, int l, int r, ll k) {
        if (In(p, l, r)) { push_tag(p, k); return ; }
        push_down(p);
        if (l <= mid)  update(lc, l, r, k);
        if (r > mid)  update(rc, l, r, k);
        tr[p] = merge(tr[lc], tr[rc]);
    }
    Tree query(int p, int l, int r) {
        if (In(p, l, r))  return tr[p];
        push_down(p);
        if (r <= mid)  return query(lc, l, r);
        if (l > mid)  return query(rc, l, r);
        return merge(query(lc, l, r), query(rc, l, r));
    }
    #undef lc
    #undef rc
    #undef mid
} SGT;
void dfs3(int u) {
    Seg_Tree :: Tree tr = SGT.query(1, 1, n); int A = tr.A, B = tr.B; ll x, y, val_A = tr.val_A, val_B = tr.val_B;
    for (P v : qry[u])  x = T[1].dist(v.F, A), y = T[1].dist(v.F, B), ans[v.S] = max(x + val_A, y + val_B);
    for (P v : T[0].G[u])  if (v.F ^ T[0].fa[u])  SGT.update(1, 1, n, v.S), SGT.update(1, T[0].dfn[v.F], T[0].dfn[v.F] + T[0].sz[v.F] - 1, - 2ll * v.S), dfs3(v.F), SGT.update(1, 1, n, - v.S), SGT.update(1, T[0].dfn[v.F], T[0].dfn[v.F] + T[0].sz[v.F] - 1, 2ll * v.S);
}
inline void solve() {
    n = rd(), q = rd(), T[0].clear(), T[1].clear(); int u, v, w;
    _for (i, 1, n)  qry[i].clear();
    _for (o, 0, 1)  _for (i, 2, n)  u = rd(), v = rd(), w = rd(), T[o].G[u].pb(mp(v, w)), T[o].G[v].pb(mp(u, w));
    _for (o, 0, 1)  T[o].dfs1(1), T[o].dfs2(1, 1), T[o].pre_work();
    SGT.build(1, 1, n);
    _for (i, 1, q)  u = rd(), v = rd(), qry[u].push_back(mp(v, i));
    _for (i, 1, n)  sort(qry[i].begin(), qry[i].end());
    dfs3(1);
    _for (i, 1, q)  write(ans[i], '\n');
}
int main() {
    ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve();
    fwrite(obuf, p3 - obuf, 1, stdout);
    return 0;
}