此博客停更

传送门-->http://www.lydsy.com/JudgeOnline/problem.php?id=3772

坑没怎么填， 写篇题解 凑凑数

促使我写这题题解的动力是网上题解都是什么$dfs$序+主席树，看到都忍不住笑出声

首先明确，一条路径被另外一条路径包含时只有两种情况，设两条路径$(x,y)$，$(u,v)$，判断$(x,y)$是否被$(u,v)$包含，强制$y$深度小于$x$，则分情况：

$I$：$y$为$x$的祖先，$z$为$x$到$y$路径上$y$下面那个点，则可以知道，包含它的路径一头在$x$的子树里，另一头不在$z$的子树里，于是可以分成两个矩形

$II$：$x$与$y$不 构成先辈关系，则一头在$x$的子树里，另一头在$y$的子树里，可以构成一个矩形

然后就把所有矩形映射到二维平面上，再把所有路径两头作为二维点同样映射到平面上，于是一条路径$(x,y)$被包含的数目就是平面上二维点被几个矩形包含，所以$Ans$便为所有二维点被几个矩形包含的和减去的二维点个数（因为同时有同一条路径构出的矩形和二维点），扫描线即可

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 100010
int i,j,k,m,n,x,y,cnt,last[N],fa[N],top[N],t,in[N],ot[N],sz[N],son[N],now,dep[N],rk[N],m2,m1,ans[N<<1],v[N];
struct edge{int to,next;}e[N<<1];ll Ans,nm;
struct line{int h,l,r,v;bool operator <(const line&b)const{return h<b.h;}}T[N<<2];
struct point{int x,y,id;bool operator <(const point&b)const{return x<b.x;}}C[N<<1];
inline void add(int u,int v){
	e[++cnt]=(edge){v,last[u]},last[u]=cnt;
	e[++cnt]=(edge){u,last[v]},last[v]=cnt;
}
void dfs1(int x,int d){
	dep[x]=d,sz[x]=1;
	for(int i=last[x],y;i;i=e[i].next)if((y=e[i].to)!=fa[x]){
		fa[y]=x,dfs1(y,d+1),sz[x]+=sz[y];
		if(sz[y]>sz[son[x]])son[x]=y;
	}
}void dfs2(int x,int d){
	top[x]=d,rk[in[x]=++now]=x;if(son[x])dfs2(son[x],d);
	for(int i=last[x],y;i;i=e[i].next)if((y=e[i].to)!=fa[x]&&y!=son[x])dfs2(y,y);ot[x]=now;
}
inline int up(int x,int k){
	if(k<0)return x;
	while(top[x]!=1)if(dep[x]-dep[top[x]]<k)k-=dep[x]-dep[top[x]]+1,x=fa[top[x]];else return rk[in[x]-k];
	return rk[in[x]-k];
}
inline void Add(int x,int d){for(;x<=n;v[x]+=d,x+=x&-x);}
inline int ask(int x){int ret=0;for(;x;ret+=v[x],x-=x&-x);return ret;}
int main(){
	for(n=read(),m=read(),i=1;i<n;++i)add(read(),read());
	for(dfs1(1,0),dfs2(1,1),i=1;i<=m;++i){
		x=read(),y=read();
		if(dep[x]<dep[y])swap(x,y);
		C[++m2]=(point){in[x],in[y],i};if(x!=y)C[++m2]=(point){in[y],in[x],i};
		if(in[x]>=in[y]&&in[x]<=ot[y]){
			t=(x!=y),y=up(x,dep[x]-dep[y]-1);
			int u=in[x],v=ot[x],l=1,r=in[y]-t;
			if(l<=r)T[++m1]=(line){u,l,r,1},T[++m1]=(line){v+1,l,r,-1};
			l=ot[y]+1,r=n;
			if(l<=r)T[++m1]=(line){u,l,r,1},T[++m1]=(line){v+1,l,r,-1};
		}else{
			int u=in[x],v=ot[x],l=in[y],r=ot[y];
			if(l<=r)T[++m1]=(line){u,l,r,1},T[++m1]=(line){v+1,l,r,-1};
		}
	}
	for(sort(T+1,T+m1+1),sort(C+1,C+m2+1),i=j=1;i<=m2;++i){
		while(j<=m1&&T[j].h<=C[i].x)Add(T[j].l,T[j].v),Add(T[j].r+1,-T[j].v),++j;
		ans[C[i].id]+=ask(C[i].y);
	}
	for(i=1;i<=m;++i)Ans+=ans[i];Ans-=m,nm=1ll*m*(m-1)/2;
	ll gcd=__gcd(Ans,nm);printf("%lld/%lld\n",Ans/gcd,nm/gcd);
}

loading...