代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
vector<int> v[N];
int son[N],siz[N],top[N],dep[N],fa[N],dfn[N],df;
int n,m,q;
void dfs1(int u,int f){
	fa[u]=f;
	siz[u]=1;
	dep[u]=dep[f]+1;
	for(auto i:v[u]){
		if(i!=f){
			dfs1(i,u);
			if(siz[i]>siz[son[u]]) son[u]=i;
			siz[u]+=siz[i];
		}
	}
}
void dfs2(int u,int tp){
	top[u]=tp;
	dfn[u]=++df;
	if(son[u]) dfs2(son[u],tp);
	for(auto i:v[u])
		if(i!=fa[u]&&i!=son[u]) dfs2(i,i);
}
struct Node{
	int l,r;
	mutable long long v;
}link[N];
struct query{
	int id;
	int l,r;
	long long ans;
}Q[N];
long long tr[N];
set<Node> odt;
bool operator<(Node p1,Node p2){
	return p1.l<p2.l;
}
int lowbit(int x){
	return x&-x;
}
void add(int x,int k){
	for(;x<=n;x+=lowbit(x)) tr[x]+=k;
}
long long ask(int x){
	long long ans=0;
	for(;x;x-=lowbit(x)) ans+=tr[x];
	return ans;
}
auto split(int x){
	auto xx=odt.lower_bound({x,0,0ll});
	if(xx!=odt.end()&&xx->l==x) return xx;
	xx--;
	int l=xx->l,r=xx->r,v=xx->v;
	odt.erase(xx);
	odt.insert({l,x-1,v});
	return odt.insert({x,r,v}).first;
}
void assign(int l,int r,long long v){
	auto fqr=split(r+1),fql=split(l);
	for(auto i=fql;i!=fqr;i++){
		if(i->v) add(i->v,i->l-i->r-1);
		add(v,i->r-i->l+1);
	}
	odt.erase(fql,fqr);
	odt.insert({l,r,v});
}
void Change(int u,int v,int val){
	while(top[u]!=top[v]){
		if(dep[fa[top[u]]]<dep[fa[top[v]]]) swap(u,v);
		assign(dfn[top[u]],dfn[u],val);
		u=fa[top[u]];
	}
	if(dep[u]>dep[v]) swap(u,v);
	assign(dfn[u],dfn[v],val);
}
int cmp1(query q1,query q2){
	if(q1.r==q2.r) return q1.l<q2.l;
	return q1.r<q2.r;
}
int cmp2(query q1,query q2){
	return q1.id<q2.id;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	n=m=q=1e5;
	for(int i=2;i<=n;i++){
		int x=rng()%(i-1)+1;
		v[x].emplace_back(i),v[i].emplace_back(x);
	}
	dfs1(1,0);
	dfs2(1,1);
	odt.insert({1,n,0});
	for(int i=1;i<=m;i++){
		int x=rng()%n+1,y=rng()%n+1;
		link[i]={x,y,0};
	}
	for(int i=1;i<=q;i++){
		int x=rng()%m+1,y=rng()%m+1;
		if(x>y) swap(x,y);
		Q[i]={i,x,y,0};
	}
	sort(Q+1,Q+q+1,cmp1);
	int j=1;
	for(int i=1;i<=m;i++){
		Change(link[i].l,link[i].r,i);
		while(j<=q&&Q[j].r==i) Q[j].ans=ask(Q[j].r)-ask(Q[j].l-1),j++;
	}
	sort(Q+1,Q+q+1,cmp2);
	for(int i=1;i<=q;i++) cout<<Q[i].ans<<'\n';
}

评测结果