XCPC wiki - 树 03 - 树直径

两次 DFS 求树直径

时空复杂度$\Theta(n)$。

vector<int> p(n), path;
auto find = [&](int s) {
    vector<int> dep(n, -1);
    auto dfs = [&](this auto&& dfs, int u) -> void {
        for (auto v : E[u]) {
            if (~dep[v]) continue;
            dep[v] = dep[u] + 1;
            // 如果带点权 dep[v] = dep[u] + val[v];
            // 如果带边权 dep[v] = dep[u] + w;
            p[v] = u;
            dfs(v);
        }
    };
    p[s] = -1;
    dep[s] = 0;  // 如果带点权 dep[s] = val[s];
    dfs(s);
    return max_element(dep.begin(), dep.end()) - dep.begin();
};
for (int u = find(find(0)); ~u; u = p[u]) {
    path.push_back(u);
}

树形 DP 求树直径

维护最长链 dp1 和次长链 dp2。

vector<int> dp1(n), dp2(n);
int d = 0;
auto dfs = [&](this auto&& dfs, int u, int p) -> void {
    dp1[u] = dp2[u] = 0;
    for (auto v : E[u]) {
        if (v == p) continue;
        dfs(v, u);
        int t = dp1[v] + 1;
        if (t > dp1[u]) dp2[u] = dp1[u], dp1[u] = t;
        else if (t > dp2[u]) dp2[u] = t;
    }
    d = max(d, dp1[u] + dp2[u]);
};
dfs(0, -1);

动态树直径

即是求$\max\limits_{u,v}\lbrace d_{u}+d_{v}-2d_{\operatorname{lca}(u,v)} \rbrace$，这很难直接维护。

全 DFS 序 DFS 遍历一棵树，每次访问到一个节点就把它记到序列末端，同时，每当一个节点的子树的访问正式结束，我们也把它的父亲记到序列末端。

例如树 1 2 2 的全 DFS 序是 1 2 3 2 4 2 1。

通俗地说，就是从根开始走，经过的所有节点构成全 DFS 序。全 DFS 序相邻两项为父子关系。

全 DFS 序可以求 LCA 的深度，即是$u$ 到$v$ 的这一段区间中所有节点的深度的最小值。

问题化为，在全 DFS 序中依次找三个点$a,b,c$，满足$d_{a}-2d_{b}+d_{c}$ 最大，此时，找到的这三个点一定是$u,\operatorname{lca},v$（否则如果$b$ 不是$a$ 和$c$ 的 LCA，会$d_{a}-2d_{b}+d_{c}$ 存在更大的值）。

用线段树维护全 DFS 序的深度。

int rt, L, R;
struct SMT {
    int pcnt;
    struct info {
        ll a, b, c, ab, bc, abc;
        ll mrk;
        int l, r;
    } t[N << 3];

    void init(int l, int r) {
        pcnt = 0, rt = 0;
        L = l, R = r;
    }

    void init(int p) {
        t[p] = { 0, 0, 0, 0, 0, 0, 0, 0 };
    }

#define ls t[p].l
#define rs t[p].r
#define mid ((cl+cr)>>1)
#define len (cr-cl+1)
#define lson ls,cl,mid
#define rson rs,mid+1,cr

    void push_up(info& p, info l, info r) {
        p.a = max(l.a, r.a);
        p.b = max(l.b, r.b);
        p.c = max(l.c, r.c);
        p.ab = max({ l.ab, r.ab, l.a + r.b });
        p.bc = max({ l.bc, r.bc, l.b + r.c });
        p.abc = max({ l.abc, r.abc, l.ab + r.c, l.a + r.bc });
    }

    void push_down(info& p, ll d, int l) {
        p.a += d;
        p.b -= 2 * d;
        p.c += d;
        p.ab -= d;
        p.bc -= d;
        p.mrk += d;
    }

    void push_up(int p) { push_up(t[p], t[ls], t[rs]); }
    void push_down(int p, int l) {
        push_down(t[ls], t[p].mrk, l - (l >> 1));
        push_down(t[rs], t[p].mrk, l >> 1);
        t[p].mrk = 0;
    }

    void build(auto& arr, int& p = rt, int cl = L, int cr = R) {
        p = ++pcnt, init(p);
        if (cl == cr) return push_down(t[p], arr[cl], 1);
        build(arr, lson), build(arr, rson);
        return push_up(p);
    }

    void modify(int l, int r, ll d, int& p = rt, int cl = L, int cr = R) {
        if (l <= cl && cr <= r) return push_down(t[p], d, len);
        push_down(p, len);
        if (l <= mid) modify(l, r, d, lson);
        if (mid < r)  modify(l, r, d, rson);
        return push_up(p);
    }

    info query(int l, int r, int& p = rt, int cl = L, int cr = R) {
        if (l <= cl && cr <= r) return t[p];
        push_down(p, len);
        if (r <= mid) return query(l, r, lson);
        if (mid < l)  return query(l, r, rson);
        info res;
        push_up(res, query(l, r, lson), query(l, r, rson));
        return res;
    }
} smt;

vector<pair<int, int>> E[N];  // [v, id]
int son[N];  // 边对应的另一端点 
ll w[N];     // 边权 
ll dep[N];
int tfn[N], tfnR[N], tseq[N << 1], tunix;  // 全 DFS 序 
void dfs(int u, int p) {
    tseq[++tunix] = u;
    tfn[u] = tunix;
    for (auto& [v, id] : E[u]) {
        if (v == p) continue;
        son[id] = v;
        dep[v] = dep[u] + w[id];
        dfs(v, u);
        tseq[++tunix] = u;
    }
    tfnR[u] = tunix;
}

void init() {
    dfs(1, 0);
    smt.init(1, tunix);
    vector<ll> arr(tunix + 1);
    for (int i = 1; i <= tunix; i++) {
        arr[i] = dep[tseq[i]];
    }
    smt.build(arr);
}

void change(int id, ll e) {
    int v = son[id];
    smt.modify(tfn[v], tfnR[v], -w[id]);
    w[id] = e;
    smt.modify(tfn[v], tfnR[v], w[id]);
}

ll get() {
    return smt.query(1, tunix).abc;
}

void eachT() {
    int n = read(), q = read();
    ll mwx = read();

    for (int id = 1; id < n; id++) {
        int u = read(), v = read();
        w[id] = read();
        E[u].emplace_back(v, id);
        E[v].emplace_back(u, id);
    }

    init();

    ll lstans = 0;
    while (q--) {
        int id = (read() + lstans % (n - 1)) % (n - 1) + 1;
        ll e = (read() + lstans % mwx) % mwx;
        change(id, e);
        printf("%lld\n", lstans = get());
    }
}