CF1192B Dynamic Diameter
题目大意
有一个 (n) 个点的带权无向树，(q) 次操作，每次修改一条边的权值，要求在每次修改后，输出树的直径大小，强制在线。
数据范围：(1leq n, qleq 10^5)。
本题题解
介绍一种简单易懂的 (mathcal{O}(q log^2 n)) 做法。
首先，有一个众所周知的结论是：对于树上任意两个点集 (S, T)，设 (S) 的直径为 ((u_S, v_S))，(T) 的直径为 ((u_T, v_T))，则点集 (Scup T) 的直径，两个端点都在 ({u_S, v_S, u_T, v_T}) 中产生。也就是说，我们在合并两个点集，并维护直径时，只需要讨论 (mathcal{O}(1)) 种可能的直径。
在 dfs 序上建一棵线段树。线段树的每个区间 ([l,r])，维护 dfs 序在 ([l,r]) 内的这些点组成的点集的直径。
考虑修改一条边的权值，会对线段树上哪些点集产生影响。设修改的边的儿子节点为 (x)，记以 (x) 为根的子树的 dfs 序区间为 ([ ext{st}_x, ext{ed}_x])。则线段树上一段区间 ([l,r]) 的答案可能发生改变，仅当 ([l,r]) 与 ([ ext{st}_x, ext{ed}_x]) 有交且不被 ([ ext{st}_x, ext{ed}_x]) 完全包含。因为无交时，说明整个点集都在子树外，肯定不会被影响到；被完全包含，说明整个点集都在子树内，也不会被影响到。
考虑“有交且不被包含”，其实就相当于，在线段树上定位 ([ ext{st}_x, ext{ed}_x]) 时，所经过的所有非终点节点。这样的节点只有 (mathcal{O}(log n)) 个，只需要对它们的直径进行更新即可。
更新时，还是从儿子那里继承，然后分类讨论。此时涉及到求树上某条路径的长度，可以使用树链剖分 + 树状数组或线段树维护（支持单点修改），这样查询是 (mathcal{O}(log n)) 的。
总时间复杂度 (mathcal{O}(n + q log^2 n))。
参考代码
// problem: CF1192B
#include <bits/stdc++.h>
using namespace std;
#define mk make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
template<typename T> inline void ckmax(T& x, T y) { x = (y > x ? y : x); }
template<typename T> inline void ckmin(T& x, T y) { x = (y < x ? y : x); }
const int MAXN = 1e5;
int n, q;
ll w;
struct InputEdge {
int u, v;
ll w;
} e[MAXN + 5];
struct ForwardStarEdge {
int nxt, to;
ll w;
} edge[MAXN * 2 + 5];
int head[MAXN + 5], tot;
inline void add_edge(int u, int v, ll w) {
edge[++tot].nxt = head[u];
edge[tot].to = v;
edge[tot].w = w;
head[u] = tot;
}
namespace TreeChainPartition {
int fa[MAXN + 5], sz[MAXN + 5], son[MAXN + 5], dep[MAXN + 5];
ll fw[MAXN + 5];
void dfs1(int u) {
sz[u] = 1;
for (int i = head[u]; i; i = edge[i].nxt) {
int v = edge[i].to;
if (v == fa[u])
continue;
fa[v] = u;
fw[v] = edge[i].w;
dep[v] = dep[u] + 1;
dfs1(v);
sz[u] += sz[v];
if (!son[u] || sz[v] > sz[son[u]])
son[u] = v;
}
}
int top[MAXN + 5], dfn[MAXN + 5], ofn[MAXN + 5], rev[MAXN + 5], cnt_dfn;
void dfs2(int u, int t) {
top[u] = t;
dfn[u] = ++cnt_dfn;
rev[cnt_dfn] = u;
if (son[u])
dfs2(son[u], t);
for (int i = head[u]; i; i = edge[i].nxt) {
int v = edge[i].to;
if (v == fa[u] || v == son[u])
continue;
dfs2(v, v);
}
ofn[u] = cnt_dfn;
}
int get_lca(int u, int v) {
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]])
swap(u, v);
u = fa[top[u]];
}
return (dep[u] < dep[v]) ? u : v;
}
struct FenwickTree {
ll c[MAXN + 5];
void point_add(int p, ll v) {
for (int i = p; i <= n; i += (i & (-i))) {
c[i] += v;
}
}
ll presum_query(int p) {
ll res = 0;
for (int i = p; i; i -= (i & (-i))) {
res += c[i];
}
return res;
}
ll range_sum_query(int l, int r) {
return presum_query(r) - presum_query(l - 1);
}
FenwickTree() {}
} T;
ll get_dist(int u, int v) {
ll res = 0;
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]])
swap(u, v);
res += T.range_sum_query(dfn[top[u]], dfn[u]);
u = fa[top[u]];
}
if (dep[u] != dep[v]) {
if (dep[u] > dep[v])
swap(u, v);
res += T.range_sum_query(dfn[u] + 1, dfn[v]);
}
return res;
}
} // namespace TreeChainPartition
struct Dia {
int u, v;
ll len;
Dia() {}
Dia(int _u, int _v) {
u = _u;
v = _v;
len = TreeChainPartition :: get_dist(u, v);
}
};
bool cmp(Dia lhs, Dia rhs) {
return lhs.len < rhs.len;
}
Dia operator + (Dia lhs, Dia rhs) {
static Dia t[10];
t[0] = lhs;
t[1] = rhs;
t[2] = Dia(lhs.u, rhs.u);
t[3] = Dia(lhs.u, rhs.v);
t[4] = Dia(lhs.v, rhs.u);
t[5] = Dia(lhs.v, rhs.v);
sort(t, t + 6, cmp);
return t[5];
}
Dia dia[MAXN * 4 + 5];
void build(int p, int l, int r) {
if (l == r) {
int u = TreeChainPartition :: rev[l];
dia[p] = Dia(u, u);
return;
}
int mid = (l + r) >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
dia[p] = dia[p << 1] + dia[p << 1 | 1];
}
void modify(int p, int l, int r, int ql, int qr) {
// 与 ql, qr 相交但未被完全包含的区间
if (ql <= l && qr >= r) {
return;
}
int mid = (l + r) >> 1;
if (ql <= mid) {
modify(p << 1, l, mid, ql, qr);
}
if (qr > mid) {
modify(p << 1 | 1, mid + 1, r, ql, qr);
}
dia[p] = dia[p << 1] + dia[p << 1 | 1];
}
int main() {
cin >> n >> q >> w;
for (int i = 1; i < n; ++i) {
cin >> e[i].u >> e[i].v >> e[i].w;
add_edge(e[i].u, e[i].v, e[i].w);
add_edge(e[i].v, e[i].u, e[i].w);
}
#define TCP TreeChainPartition
TCP :: dfs1(1);
TCP :: dfs2(1, 1);
for (int i = 2; i <= n; ++i) {
TCP :: T.point_add(TCP :: dfn[i], TCP :: fw[i]);
}
build(1, 1, n);
ll last_ans = 0;
for (int tq = 1; tq <= q; ++tq) {
int id;
ll neww;
cin >> id >> neww;
id = ((ll)id + last_ans) % (n - 1) + 1;
neww = (neww + last_ans) % w;
int u = e[id].u;
if (TCP :: fa[u] != e[id].v) {
u = e[id].v;
assert(TCP :: fa[u] == e[id].u);
}
TCP :: T.point_add(TCP :: dfn[u], neww - TCP :: fw[u]);
TCP :: fw[u] = neww;
modify(1, 1, n, TCP :: dfn[u], TCP :: ofn[u]);
cout << (last_ans = dia[1].len) << endl;
}
#undef TCP
return 0;
}