原題鏈接

解析

首先將直徑長度轉換為深度，那么要求的就是：

修改邊權啟發我們在 DFS 序上考慮，因為修改邊權影響的是子樹內結點的深度，在 DFS 序上就對應著一段連續的區間，可以用線段樹來維護。如果你知道如何利用 DFS 序來求 LCA，那么你應該知道如果令 \(a_i\) 表示 DFS 序編號為 \(i\) 的點的父親的深度，有：

如果再令 \(b_i\) 表示 DFS 序編號為 \(i\) 的點的深度，那么DFS 序編號為 \(u,v\) 的兩點之間長度就可以表示為：

在前面加個 \(\max\) 就是直徑了：

可以發現，如果把 \(\min\) 提出來，依然能保證取到最大值時 \(i\) 是 \(u,v\) 的 LCA，于是最終要維護的式子就變成了：

線段樹上維護即可，詳見代碼。

時間復雜度 \(O(n \log n)\)

代碼

/*
*/
#include<bits/stdc++.h>
#define eps 0.000001
#define mid ((l + r) >> 1)
#define ls(x) ((x) << 1)
#define rs(x) (((x) << 1) | 1)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<ll,int> pii;
const int N = 1e5 + 5,M = 3.2e4 + 5;
int head[N << 1],to[N << 1],nxt[N << 1],from[N << 1],ecnt,dfn[N],cnt,fa[N],siz[N],rev[N];
ll val[N << 1],dep[N],fdep[N]//dep,fdep 分別對應上文中的 a,b
ll ans[N << 2],mn[N << 2],mx[N << 2],lx[N << 2],rx[N << 2],tag[2][N << 2];
void add(int u,int v,ll w){
	ecnt++;
	from[ecnt] = u;
	to[ecnt] = v;
	nxt[ecnt] = head[u];
	val[ecnt] = w;
	head[u] = ecnt;
}
void dfs(int x,int f){
	fdep[x] = dep[f];
	dfn[x] = ++cnt;
	rev[cnt] = x;
	siz[x] = 1;
	for(int i=head[x];i;i=nxt[i])if(to[i] != f){
		dep[to[i]] = dep[x] + val[i];
		dfs(to[i],x);
		siz[x] += siz[to[i]];
	}
}
void push_up(int p,int l,int r){
	mn[p] = min(mn[ls(p)],mn[rs(p)]);//最小 a
	mx[p] = max(mx[ls(p)],mx[rs(p)]);//最大 b
	lx[p] = max({lx[ls(p)],lx[rs(p)],mx[ls(p)] - 2 * mn[rs(p)]});//最大 b_u + a
	rx[p] = max({rx[ls(p)],rx[rs(p)],mx[rs(p)] - 2 * mn[ls(p)]});//最大 a + b_v
	ans[p] = max({ans[ls(p)],ans[rs(p)],lx[ls(p)] + mx[rs(p)],rx[rs(p)] + mx[ls(p)]});
}
void build(int p,int l,int r){
	if(l == r){
		mn[p] = fdep[rev[l]];
		mx[p] = dep[rev[l]];
		lx[p] = -2e18;//長度為 1 的區間不存在 lx
		rx[p] = dep[rev[l]] - 2 * fdep[rev[l]];
		ans[p] = 0;
		return;
	}
	build(ls(p),l,mid),build(rs(p),mid + 1,r);
	push_up(p,l,r);
}
void add_tag(int p,ll k,int op){
	if(op){
		mn[p] += k;
		lx[p] -= lx[p] <= -2e18 ? 0 : 2 * k;
		rx[p] -= 2 * k;
	}else{
		lx[p] += lx[p] <= -2e18 ? 0 : k;
		rx[p] += k;
		mx[p] += k;
	}
	tag[op][p] += k;
}
void push_down(int p){
	if(!tag[0][p] && !tag[1][p]) return;
	add_tag(ls(p),tag[0][p],0);
	add_tag(ls(p),tag[1][p],1);
	add_tag(rs(p),tag[0][p],0);
	add_tag(rs(p),tag[1][p],1);
	tag[0][p] = tag[1][p] = 0;
}
void modi(int p,int l,int r,int L,int R,ll k,int op){
	if(l > R || r < L) return;
	if(l >= L && r <= R){
		add_tag(p,k,op);
		return;
	}
	push_down(p);
	modi(ls(p),l,mid,L,R,k,op),modi(rs(p),mid + 1,r,L,R,k,op);
	push_up(p,l,r); 
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out1.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int n,q;
	ll lim;
	cin>>n>>q>>lim;
	for(int i=1;i<n;i++){
		ll u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);
	}
	dfs(1,0);
	build(1,1,n);
	ll last = 0;
	while(q--){
		ll d,e;
		cin>>d>>e;
		d = (d + last) % (n - 1) + 1;
		e = (e + last) % lim;
		int u = from[d << 1],v = to[d << 1];
		ll dt = e - val[d << 1];
	 	val[d << 1] += dt;
	 	val[(d << 1) - 1] += dt;
		if(dep[u] > dep[v]) swap(u,v);
		modi(1,1,n,dfn[v],dfn[v] + siz[v] - 1,dt,0);
		modi(1,1,n,dfn[v] + 1,dfn[v] + siz[v] - 1,dt,1);
		cout<<(last = ans[1])<<'\n'; 
	}
	return 0;
}