发布时间：2025-05-22

线段树动态维护树的直径

struct SegmentTree{
	/*
	欧拉序，lca为深度最浅的点
	mx=max(dep[L,R])
	mn=min(dep[L,R])
	lmx=max(dep[x]-2*dep[y]),x<=y
	rmx=max(dep[x]-2*dep[y]),x>=y
	ans=max(dep[x]+dep[y]-2*dep[lca(x,y)])
	*/ 
	struct Node{
		int ans,mx,mn,lmx,rmx,tag;
	};
	vector<Node> t;
	void init(int n){
		t=vector<Node>(n<<2);
	}
	void pushup(int p){
		auto &u=t[p],&l=t[p<<1],&r=t[p<<1|1];
		u.ans=max({l.ans,r.ans,l.lmx+r.mx,r.rmx+l.mx});
		u.mx=max(l.mx,r.mx);
		u.mn=min(l.mn,r.mn);
		u.lmx=max({l.lmx,r.lmx,l.mx-2*r.mn});
		u.rmx=max({l.rmx,r.rmx,r.mx-2*l.mn});
	}
	void pushtag(int p,int tag){
		auto &u=t[p];
		u.mx+=tag;
		u.mn+=tag;
		u.lmx-=tag;
		u.rmx-=tag;
		u.tag+=tag;
	}
	void pushdown(int p){
		if(t[p].tag){
			pushtag(p<<1,t[p].tag);
			pushtag(p<<1|1,t[p].tag);
			t[p].tag=0;
		}
	}
	void build(int p,int l,int r,vector<int> &a){
		t[p]={-INF,-INF,INF,-INF,-INF,0};
		if(l==r){
			t[p].mx=t[p].mn=a[l];
			t[p].lmx=t[p].rmx=-a[l];
			t[p].ans=0;
			return;
		}
		int mid=l+r>>1;
		build(p<<1,l,mid,a);	
		build(p<<1|1,mid+1,r,a);
		pushup(p);
	}	
	void modify(int p,int l,int r,int ql,int qr,int x){
		if(ql<=l&&r<=qr){
			pushtag(p,x);
			return;
		}
		pushdown(p);
		int mid=l+r>>1;
		if(ql<=mid)modify(p<<1,l,mid,ql,qr,x);
		if(qr>mid)modify(p<<1|1,mid+1,r,ql,qr,x);
		pushup(p);
	}
};
void solve(){
	int n,q,W;
	cin>>n>>q>>W;
	vector<vector<PII>> adj(n+1);
	vector<array<int,3>> edges(n);
	vector<int> dep(n+1),fir(n+1),lst(n+1),seq(2*n+1);
	for(int i=1;i<n;i++){
		int u,v,w;
		cin>>u>>v>>w;
		edges[i]={u,v,w};
		adj[u].push_back({v,w});
		adj[v].push_back({u,w});
	}
	SegmentTree t;
	int dfc=0;
	auto dfs=[&](auto &&self,int u,int fa)->void{
		seq[++dfc]=dep[u];
		fir[u]=dfc;
		for(auto [v,w]:adj[u]){
			if(v==fa)continue;
			dep[v]=dep[u]+w;
			self(self,v,u);
			seq[++dfc]=dep[u];
		}
		lst[u]=dfc;
	};
	dfs(dfs,1,0);
	t.init(dfc);
	t.build(1,1,dfc,seq);
	int ans=0;
	while(q--){
		int d,e;
		cin>>d>>e;
		d=(d+ans)%(n-1)+1;
		e=(e+ans)%W;
		auto &[u,v,w]=edges[d];
		if(fir[u]>fir[v])swap(u,v);
		int l=fir[v],r=lst[v];
		t.modify(1,1,dfc,l,r,e-w);
		w=e;
		ans=t.t[1].ans;
		cout<<ans<<"\n";
	}
}

LCT维护森林中每颗树的直径

记录每个连通块的的直径端点和长度

询问两点$u,v$的长度就是split后的$sz-1$

如果有边权则，边权转点权

但是这个做法只能加边，无法断边