P6845

· · 题解

朴素的 dfs 求直径好像很难拓展的样子……

DP 求直径好像动态 dp 也可以搞，但很复杂的样子……

所以考虑用数据结构优化暴力求直径！

即快速且动态地求出：

\max_{x=1}^n\max_{y=1}^ndis_{x,y}

利用树上差分基本功不难知道其等价于：

=\max_{x=1}^n\max_{y=1}^n(dep_x+dep_y-2\cdot dep_{lca(x,y)})

既然 lca 是关于 x,y 的二元函数，那可不可以把它转化成代数语言呢？

联想 O(1) 求 lca 算法，利用欧拉序可以将 lca 转化成 RMQ 问题。即：

\mathrm{first}_{lca(x,y)}=\min_{\mathrm{any}_x\leq i\leq \mathrm{any}_y}(\mathrm{first}_{\mathrm{eul}_i})

其中，\mathrm{first}_x 为 x 的第一个欧拉序编号，\mathrm{any}_x 为 x 的任意一个欧拉序编号，\mathrm{eul}_x 为欧拉序为 x 的节点编号。

这样做的原因是 \mathrm{first}_x=\min_{y\in son(x)}\mathrm{first}_y，而注意到 dep_x=\min_{y\in son(x)}dep_y（其中 son(x) 表示 x 的子树）。所以同理可得：

dep_{lca(x,y)}=\min_{\mathrm{any}_x\leq i\leq \mathrm{any}_y}(dep_{\mathrm{eul}_i})

于是，考虑设置长度为 2n-1 的序列 a，满足 a_i=dep_{\mathrm{eul}_i}。则原式等价于：

=\max_{x=1}^{2n-1}\max_{y=x}^{2n-1}(a_x+a_y-2\cdot (\min_{x\leq z\leq y}a_z))

这是显然可以线段树维护的。

具体而言，对于每个节点维护：

lp=\max_{l\leq x\leq r}(a_x-2\cdot (\min_{x\leq z\leq r}a_z))\\ rp=\max_{l\leq y\leq r}(a_y-2\cdot (\min_{l\leq z\leq y}a_z))\\ mx=\max_{l\leq x\leq r} a_x\\ mn=\min_{l\leq x\leq r} a_x\end{cases}

则转移显然为：

ans=\max\{ans_{ls},\ ans_{rs},\ lp_{ls}+mx_{rs},\ mx_{ls}+rp_{rs}\}\\ lp=\max\{lp_{ls},\ lp_{rs},\ mx_{ls}-2\cdot mn_{rs}\}\\ rp=\max\{rp_{ls},\ rp_{rs},\ mx_{rs}-2\cdot mn_{ls}\} \end{cases}

对于边单点改，相当于是 dep 子树加，记录 \mathrm{last}_x 为 x 的最后一个欧拉序编号，对 \mathrm{first}_x\leq i\leq \mathrm{last}_x 进行区间加即可。

#include <cstdio>
#include <cstring>
#include <algorithm>

#define N 200010
#define int long long
int n, m;

int h[N], e[N << 1], ne[N << 1], id[N << 1], idx = -1;
int u_[N], v_[N], w_[N];

void add_edge(int x, int y, int id_)
{
    ne[++idx] = h[x];
    h[x] = idx;
    e[idx] = y;
    id[idx] = id_;
}

void add(int x, int y, int id_)
{
    add_edge(x, y, id_);
    add_edge(y, x, id_);
}

int our[N], first[N], last[N], dis[N];

void dfs(int k, int fa)
{
    our[++our[0]] = k;
    first[k] = our[0];
    for(int i = h[k]; ~i; i = ne[i])
    {
        int nx = e[i];
        if(nx == fa)
            continue;
        u_[id[i]] = k;
        v_[id[i]] = nx;
        dis[nx] = dis[k] + w_[id[i]];
        dfs(nx, k);
        our[++our[0]] = k;
    }
    last[k] = our[0];
}

struct Tree
{
    int mx, mn;
    int lp, rp, ans;
    int lazy;
    void push(int z)
    {
        mx += z;
        mn += z;
        lazy += z;
        lp -= z;
        rp -= z;
    }
}tr[N << 2];

#define lson k << 1
#define rson k << 1 | 1

void pushup(int k)
{
    tr[k].mx = std::max(tr[lson].mx, tr[rson].mx);
    tr[k].mn = std::min(tr[lson].mn, tr[rson].mn);
    tr[k].lp = std::max({tr[lson].lp, tr[rson].lp, tr[lson].mx - 2 * tr[rson].mn});
    tr[k].rp = std::max({tr[lson].rp, tr[rson].rp, tr[rson].mx - 2 * tr[lson].mn});
    tr[k].ans = std::max({tr[lson].ans, tr[rson].ans, tr[lson].lp + tr[rson].mx, tr[lson].mx + tr[rson].rp});
}

void pushdown(int k)
{
    if(tr[k].lazy)
    {
        tr[lson].push(tr[k].lazy);
        tr[rson].push(tr[k].lazy);
        tr[k].lazy = 0;
    }
}

#define inf 0x3f3f3f3f3f3f3f3f
#define ls lson, l, mid
#define rs rson, mid + 1, r

void build(int k, int l, int r)
{
    if(l == r)
    {
        tr[k].mn = tr[k].mx = dis[our[l]];
        tr[k].lp = tr[k].rp = -dis[our[l]];
        tr[k].ans = 0;
        return;
    }
    int mid = (l + r) >> 1;
    build(ls);
    build(rs);
    pushup(k);
}

void change(int k, int l, int r, int ql, int qr, int z)
{
    if(ql <= l && r <= qr)
    {
        tr[k].push(z);
        return;
    }
    pushdown(k);
    int mid = (l + r) >> 1;
    if(ql <= mid)
        change(ls, ql, qr, z);
    if(mid < qr)
        change(rs, ql, qr, z);
    pushup(k);
}

#define root 1, 1, n * 2 - 1

int W;

#undef int
int main()
{
#define int long long
    memset(h, -1, sizeof(h));
    scanf("%lld%lld%lld", &n, &m, &W);
    for(int i = 1; i < n; i++)
    {
        scanf("%lld%lld%lld", &u_[i], &v_[i], &w_[i]);
        add(u_[i], v_[i], i);
    }
    dfs(1, 0);
    build(root);
    int lastans = 0;
    for(int i = 1, x, y; i <= m; i++)
    {
        scanf("%lld%lld", &x, &y);
        x = (x + lastans) % (n - 1) + 1;
        y = (y + lastans) % W;
        int v = v_[x];
        int w = w_[x];
        change(root, first[v], last[v], y - w);
        printf("%lld\n", tr[1].ans);
        w_[x] = y;
        lastans = tr[1].ans;
    }
    return 0;
}