Description
Byteland 有 \(n\) 座城市，从 \(1\) 到 \(n\) 编号，且有 \(n-1\) 条双向公路和 \(n-1\) 条双向铁路连接它们。
对于任意一对城市，都可以仅通过公路互相到达；同样，仅通过铁路也能互相到达。
Alice 和 Bob 计划在 Byteland 进行 \(q\) 次长途旅行。在每次旅行中，Alice 从第 \(a\) 座城市出发，只通过公路访问一些其他城市；Bob 从第 \(b\) 座城市出发，只通过铁路访问一些其他城市。
两人最终会在同一座目的城市会合，并且在整个旅途中都不会重复访问任何城市。
你需要求出，在所有目的城市的选择中，他们路线总长度的最大值。
\(n\leq 10^5,q\leq 5\times 10^5\)。
Solution
首先对于一棵树，每次求距离某个点最远的点，有两种做法，第一种是离线下来用数据结构维护距离；第二种方法是由于最远的点一定是直径端点，所以可以求出全局直径后 \(O(1)\) 做。
这里有两棵树，用某一种方法都不太好做，考虑将这两种方法结合起来。
先把询问离线下来，对第一棵树做第一种方法，即按照 dfs 的顺序枚举询问在第一棵树的点 \(x\)，在移动的过程中维护 \(w_i\) 表示 \(i\) 与 \(x\) 的距离。
现在问题等价于求 \(w_i+dis_2(i,y)\) 的最大值，这个对第二棵树的每个点 \(j\)，建立一个虚点 \(j'\)，与 \(j\) 连边权值为 \(w_j\) 就能将问题转化为直径问题。
但是移动 \(x\) 的过程中 \(w_i\) 会变化，考虑用线段树维护子树内节点的直径。
注意到线段树修改的过程是找到若干个线段树区间 \([l,r]\) 再区间打标记，由于整体打标记不会影响直径，所以找到这些区间后向上合并直径就行了。
时间复杂度：\(O(n\log n+q)\)。
Code
#include <bits/stdc++.h>#define int int64_tusing pii = std::pair<int, int>;const int kMaxN = 1e5 + 5, kMaxQ = 5e5 + 5;int n, q, pos;
int res[kMaxQ];
std::vector<std::pair<int, int>> qq[kMaxN];struct Tree {int dfn_cnt, dfn[kMaxN], idx[kMaxN], sz[kMaxN], dis[kMaxN], st[kMaxN][18];std::vector<std::pair<int, int>> G[kMaxN];int get(int x, int y) { return dfn[x] < dfn[y] ? x : y; }void add(int u, int v, int w) { G[u].emplace_back(v, w), G[v].emplace_back(u, w); }void dfs(int u, int fa) {st[dfn[u] = ++dfn_cnt][0] = fa, idx[dfn_cnt] = u, sz[u] = 1;for (auto [v, w] : G[u]) {if (v == fa) continue;dis[v] = dis[u] + w;dfs(v, u);sz[u] += sz[v];}}int LCA(int x, int y) {if (x == y) return x;if (dfn[x] > dfn[y]) std::swap(x, y);int k = std::__lg(dfn[y] - dfn[x]);return get(st[dfn[x] + 1][k], st[dfn[y] - (1 << k) + 1][k]);}int getdis(int x, int y) { return dis[x] + dis[y] - 2 * dis[LCA(x, y)]; }void prework() {dfn_cnt = 0, dfs(1, 0);for (int i = 1; i <= std::__lg(dfn_cnt); ++i)for (int j = 1; j <= dfn_cnt - (1 << i) + 1; ++j)st[j][i] = get(st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);}
} t1, t2;int calc(int x, int y) { return t1.getdis(pos, x) + t1.getdis(pos, y) + t2.getdis(x, y); }pii merge(pii a, pii b) {if (!a.first) return b;if (!b.first) return a;std::vector<int> vec = {a.first, a.second, b.first, b.second};pii ret = {0, 0};int now = -1e9;for (int i = 0; i < 4; ++i) {for (int j = i + 1; j < 4; ++j) {int val = calc(vec[i], vec[j]);if (val > now) ret = {vec[i], vec[j]}, now = val;}}return ret;
}struct SGT {pii t[kMaxN * 4];void pushup(int x) { t[x] = merge(t[x << 1], t[x << 1 | 1]); }void build(int x, int l, int r) {if (l == r) return void(t[x] = {t1.idx[l], t1.idx[l]});int mid = (l + r) >> 1;build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);pushup(x);}void update(int x, int l, int r, int ql, int qr) {if (l > qr || r < ql) return;else if (l >= ql && r <= qr) return;int mid = (l + r) >> 1;update(x << 1, l, mid, ql, qr), update(x << 1 | 1, mid + 1, r, ql, qr);pushup(x);}
} sgt;void dfs(int u, int fa) {for (auto [b, id] : qq[u]) {auto [x, y] = sgt.t[1];res[id] = std::max({res[id], t1.getdis(x, u) + t2.getdis(x, b), t1.getdis(y, u) + t2.getdis(y, b)});}for (auto [v, w] : t1.G[u]) {if (v == fa) continue;pos = v, sgt.update(1, 1, n, t1.dfn[v], t1.dfn[v] + t1.sz[v] - 1);dfs(v, u);pos = u, sgt.update(1, 1, n, t1.dfn[v], t1.dfn[v] + t1.sz[v] - 1);}
}void dickdreamer() {std::cin >> n >> q;for (int i = 1; i < n; ++i) {int u, v, w;std::cin >> u >> v >> w;t1.add(u, v, w);}for (int i = 1; i < n; ++i) {int u, v, w;std::cin >> u >> v >> w;t2.add(u, v, w);}for (int i = 1; i <= q; ++i) {int a, b;std::cin >> a >> b;qq[a].emplace_back(b, i);}t1.prework(), t2.prework();pos = 1, sgt.build(1, 1, n);dfs(1, 0);for (int i = 1; i <= q; ++i) std::cout << res[i] << '\n';
}int32_t main() {
#ifdef ORZXKRfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifstd::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);int T = 1;// std::cin >> T;while (T--) dickdreamer();// std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";return 0;
}