本文共 3342 字，大约阅读时间需要 11 分钟。

题目

思路

直径的合并是 $4\times \mathcal{O}($ 求 $\mathtt{l}\mathtt{c}\mathtt{a}$ $)$ 的。线段树，结束。

代码

#include <cstdio>#include <iostream>#include <vector>using namespace std;inline int readint(){   	int a = 0; char c = getchar(), f = 1;	for(; c<'0'||c>'9'; c=getchar())		if(c == '-') f = -f;	for(; '0'<=c&&c<='9'; c=getchar())		a = (a<<3)+(a<<1)+(c^48);	return a*f;}const int MaxN = 100005;struct Edge{   	int to, nxt; long long val;	Edge(){    }	Edge(int T,int N,long long V){   		to = T, nxt = N, val = V;	}};Edge e[MaxN<<1];int head[MaxN], cntEdge;void addEdge(int a,int b,long long c){   	e[cntEdge] = Edge(b,head[a],c);	head[a] = cntEdge ++;}int n, fa[MaxN][20], dep[MaxN];int st[MaxN], ed[MaxN], dfn;int pos[MaxN]; // st[pos[x]] = xnamespace BIT{   	long long c[MaxN];	void modify(int id,long long v){   		for(int i=id; i<=n; i+=(i&-i))			c[i] += v; // simple	}	long long query(int id){   		long long sum = 0;		for(int i=id; i; i-=(i&-i))			sum += c[i];		return sum;	}}void build(int x=1,long long len=0){   	st[x] = ++ dfn; pos[dfn] = x;	for(int j=0; fa[x][j]; ++j)		fa[x][j+1] = fa[fa[x][j]][j];	for(int i=head[x]; ~i; i=e[i].nxt)		if(e[i].to != fa[x][0]){   			fa[e[i].to][0] = x;			dep[e[i].to] = dep[x]+1;			build(e[i].to,e[i].val);		}	ed[x] = dfn;	BIT::modify(st[x],len);	BIT::modify(ed[x]+1,-len);}int getLca(int a,int b){   	if(dep[a] < dep[b]) swap(a,b);	for(int j=19; ~j; --j)		if((dep[a]-dep[b])>>j&1)			a = fa[a][j];	if(a == b) return a;	for(int j=19; ~j; --j)		if(fa[a][j] != fa[b][j]){   			a = fa[a][j];			b = fa[b][j];		}	return fa[a][0];}long long getDis(int a,int b){   	return BIT::query(st[a])+BIT::query(st[b])		-(BIT::query(st[getLca(a,b)])<<1);}struct Diameter{   	int a[2]; long long dis;	Diameter operator & (const Diameter &t) const {   		Diameter c = *this;		if(dis < t.dis) c = t;		for(int i=0; i<2; ++i)		for(int j=0; j<2; ++j){   			int xez = getDis(a[i],t.a[j]);//			printf("dis(%d,%d) = %d\n",a[i],t.a[j],xez);			if(c.dis < xez){   				c.dis = xez;				c.a[0] = a[i];				c.a[1] = t.a[j];			}		}		return c;	}};namespace SgTree{   	Diameter val[MaxN<<2];	void build(int o=1,int l=1,int r=n){   		if(l == r){   			val[o].a[0] = pos[l];			val[o].a[1] = pos[r];			val[o].dis = 0; return ;		}		build(o<<1,l,(l+r)>>1);		build(o<<1|1,(l+r)/2+1,r);		val[o] = val[o<<1]&val[o<<1|1];	}	void modify(int ql,int qr,int o=1,int l=1,int r=n){   		if(ql <= l && r <= qr) return ;		if(ql <= ((l+r)>>1))			modify(ql,qr,o<<1,l,(l+r)>>1);		if(((l+r)>>1) < qr)			modify(ql,qr,o<<1|1,(l+r)/2+1,r);		val[o] = val[o<<1]&val[o<<1|1];//		printf("val[%d,%d] = %d\n",l,r,val[o].dis);	}	long long query(){   		return val[1].dis;	}}int main(){   	n = readint();	int q = readint();	long long w; scanf("%lld",&w);	for(int i=1; i<=n; ++i)		head[i] = -1;	for(int i=1,a,b; i<n; ++i){   		a = readint(), b = readint();		long long xyx; scanf("%lld",&xyx);		addEdge(a,b,xyx), addEdge(b,a,xyx);	}	build(), SgTree::build();//	for(int i=1; i<=n; ++i)//		printf("pos[%d] = %d\n",i,pos[i]);	long long lst = 0;	for(int d,v; q; --q){   		d = (readint()+lst)%(n-1);		v = (readint()+lst)%w;		int x = e[d<<1|1].to;		if(dep[e[d<<1].to] > dep[x])			x = e[d<<1].to; // lower one		BIT::modify(st[x],v-e[d<<1].val);		BIT::modify(ed[x]+1,e[d<<1].val-v);		e[d<<1].val = e[d<<1|1].val = v;		SgTree::modify(st[x],ed[x]);		lst = SgTree::query();		printf("%lld\n",lst);	}	return 0;}