自动搬运

查看原文

来自洛谷，原作者为

	ningago 恋爱脑

搬运于2025-08-24 22:24:32，当前版本为作者最后更新于2023-04-17 12:43:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

朴素的 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)) $$

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

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

$$\begin{cases}ans=\max_{l\leq x\leq y\leq r}(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}$$

则转移显然为：

$$\begin{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;
}