正题

题目链接:https://www.luogu.com.cn/problem/P5327

题目大意

给出\(n\)个点的一棵树，和\(m\)条路径，求有多少个点对至少存在一条路径经过它们。

\(1\leq n,m\leq 10^5\)

解题思路

有一个很显然的性质，如果点\(z\)在\(x\rightarrow y\)的路径上，并且\((x,z)\)不合法，那么\((x,y)\)肯定不合法。

所以这样的对于一个节点\(x\)来说所有和它合法的点会形成一棵生成树，这棵生成树是哪来的也很好说，我们把所有经过\(x\)的路径\(s\rightarrow t\)的\(s\)和\(t\)存下来，构出一棵虚树，这棵虚树的大小就是对于这个点来说合法的点个数。

虚树的大小怎么求，这个方法很多，而我们尽量使用一种比较方便动态维护的方法，把所有点按照\(dfs\)序排序，假设节点\(x\)之后排的是\(y\)（定义第一个之前排的是最后一个），那么就是所有\(dep_{y}-dep_{lca(x,y)}\)的和。

不难发现这个东西可以在序列上维护，同理的可以在线段树上维护，每个区间记录\(dfs\)最小的和最大的点就好了。

那么做法已经很显然了，一条路径经过的点我们可以用树上差分来做到也就是\(s\leftrightarrow lca(s,t)\)和\(t\leftrightarrow lca(s,t)\)的部分。

然后两个子树的信息合并的时候用线段树合并就好了。

写了个\(RMQ\)来快速求\(LCA\)。

时间复杂度：\(O(n\log n)\)

code

#include
#include
#include
#include
using namespace std;
const int N=1e5+10,M=N*20*4;
struct node{
	int to,next;
}a[N<<1];
int n,m,tot,cnt,dfc,ls[N],dep[N],rt[N];
int dfn[N],rfn[N],rgn[N],lg[N<<1],f[N<<1][19];
vector v[N],g[N];
long long ans;
void addl(int x,int y){
	a[++tot].to=y;
	a[tot].next=ls[x];
	ls[x]=tot;return;
}
void dfs(int x,int fa){
	dep[x]=dep[fa]+1;
	dfn[++dfc]=x;rfn[x]=dfc;
	rgn[x]=++cnt;f[cnt][0]=x;
	for(int i=ls[x];i;i=a[i].next){
		int y=a[i].to;
		if(y==fa)continue;
		dfs(y,x);f[++cnt][0]=x;
	}
	return;
}
int LCA(int x,int y){
	int l=rgn[x],r=rgn[y];
	if(l>r)swap(l,r);
	int z=lg[r-l+1];
	x=f[l][z];y=f[r-(1<>1;
		if(pos<=mid)Change(ls[x],L,mid,pos,val);
		else Change(rs[x],mid+1,R,pos,val);
		Merge(x,ls[x],rs[x]);return;
	}
	int Merge(int x,int y,int L,int R){
		if(!x||!y)return x+y;
		if(L==R){
			w[x]=w[x]+w[y];
			if(w[x])lp[x]=rp[x]=dfn[L];
			else lp[x]=rp[x]=0;
			return x;
		}
		int mid=(L+R)>>1;
		ls[x]=Merge(ls[x],ls[y],L,mid);
		rs[x]=Merge(rs[x],rs[y],mid+1,R);
		Merge(x,ls[x],rs[x]);return x;
	}
}T;
void solve(int x,int fa){
	for(int i=ls[x];i;i=a[i].next){
		int y=a[i].to;
		if(y==fa)continue;solve(y,x);
		rt[x]=T.Merge(rt[x],rt[y],1,n);
	}
	for(int i=0;i>1]+1;
	for(int i=1,x,y;i<=m;i++){
		scanf("%d%d",&x,&y);
		v[x].push_back(rfn[x]);
		v[x].push_back(rfn[y]);
		v[y].push_back(rfn[x]);
		v[y].push_back(rfn[y]);
		int lca=LCA(x,y);
		g[lca].push_back(rfn[x]);
		g[lca].push_back(rfn[y]);
	}
	solve(1,0);
	printf("%lld\n",(ans-n)/2ll);
	return 0;
}