BZOJ 3772 精神污染

题目大意

给你一棵树和树上的一些路径，求有多少路径A包含路径B的情况。

扫描线+树状数组，代码不忍直视，注意边要depth[u]<depth[v]，不能u<v.

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
inline char nc()
{
	static char buf[100000],*p1,*p2;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int RI()
{
	int ret=0;char tmp=nc();
	while(!isdigit(tmp)) tmp=nc();
	while(isdigit(tmp)) ret=ret*10+(tmp^'0'),tmp=nc();
	return ret;
}
#define N 100010
struct edge{int u,v;}e[N];
struct point{int x,y,id;}p[N<<1];
struct query{int x,y,id,res,mus;}q[N<<3];
bool cmpp(const point &X,const point &Y){return X.x==Y.x?X.y<Y.y:X.x<Y.x;}
bool cmpq(const query &X,const query &Y){return X.x==Y.x?X.y<Y.y:X.x<Y.x;}
bool back(const query &X,const query &Y){return X.id<Y.id;}
int n,m,cq,rka[N],rkb[N],bit[N<<1],cnt,fa[N][21],depth[N],lg[N];
int to[N<<1],nxt[N<<1],head[N],tot;
inline void AE(int X,int Y){to[++tot]=Y,nxt[tot]=head[X],head[X]=tot;}
void DFS(int pos,int pre)
{
	for(int i=1;i<=lg[n];++i) fa[pos][i]=fa[fa[pos][i-1]][i-1];
	rka[pos]=++cnt;
	for(int i=head[pos];i;i=nxt[i]) if(to[i]!=pre) depth[to[i]]=depth[pos]+1,fa[to[i]][0]=pos,DFS(to[i],pos);
	rkb[pos]=++cnt;
}
inline void insert(int X){for(;X<=(n<<1);X+=X&-X) bit[X]++;}
inline int query(int X)
{
	int ret=0;
	for(;X;X-=X&-X) ret+=bit[X];
	return ret;
}
long long gcd(long long X,long long Y){return Y?gcd(Y,X%Y):X;}
bool sameline(int X,int Y)
{
	for(int i=lg[n];~i;i--) if(depth[fa[Y][i]]>=depth[X]) Y=fa[Y][i];
	return X==Y;
}
int getfa(int X,int Y)
{
	int tmp=depth[X]+1;
	for(int i=lg[n];~i;i--) if(depth[fa[Y][i]]>=tmp) Y=fa[Y][i];
	return Y;
}
int main()
{
	int X,Y;
	n=RI(),m=RI();
	for(int i=2;i<=n;++i) X=RI(),Y=RI(),AE(X,Y),AE(Y,X),lg[i]=lg[i>>1]+1;
	depth[1]=1,DFS(1,0);
	for(int i=1;i<=m;++i)
	{
		e[i].u=RI(),e[i].v=RI();
		if(depth[e[i].u]>depth[e[i].v]) swap(e[i].u,e[i].v);
	}
	for(int i=1;i<=m;++i)
	{
		p[i].id=i,p[i].x=rka[e[i].u],p[i].y=rka[e[i].v];
		p[i+m].id=i,p[i+m].x=rka[e[i].v],p[i+m].y=rka[e[i].u];
	}
	sort(p+1,p+(m<<1)+1,cmpp);
	for(int i=1;i<=m;++i)
	{
		if(sameline(e[i].u,e[i].v))
		{
			int tmp=getfa(e[i].u,e[i].v);
			++cq,q[cq].id=cq,q[cq].x=rkb[e[i].v],q[cq].y=rkb[1],q[cq].mus=1;
			++cq,q[cq].id=cq,q[cq].x=rka[e[i].v]-1,q[cq].y=rka[1]-1,q[cq].mus=1;
			++cq,q[cq].id=cq,q[cq].x=rkb[e[i].v],q[cq].y=rka[1]-1,q[cq].mus=1;
			++cq,q[cq].id=cq,q[cq].x=rka[e[i].v]-1,q[cq].y=rkb[1],q[cq].mus=1;
			++cq,q[cq].id=cq,q[cq].x=rkb[e[i].v],q[cq].y=rkb[tmp],q[cq].mus=-1;
			++cq,q[cq].id=cq,q[cq].x=rka[e[i].v]-1,q[cq].y=rka[tmp]-1,q[cq].mus=-1;
			++cq,q[cq].id=cq,q[cq].x=rkb[e[i].v],q[cq].y=rka[tmp]-1,q[cq].mus=-1;
			++cq,q[cq].id=cq,q[cq].x=rka[e[i].v]-1,q[cq].y=rkb[tmp],q[cq].mus=-1;
		}
		else
		{
			++cq,q[cq].id=cq,q[cq].x=rkb[e[i].v],q[cq].y=rkb[e[i].u],q[cq].mus=1;
			++cq,q[cq].id=cq,q[cq].x=rka[e[i].v]-1,q[cq].y=rka[e[i].u]-1,q[cq].mus=1;
			++cq,q[cq].id=cq,q[cq].x=rkb[e[i].v],q[cq].y=rka[e[i].u]-1,q[cq].mus=1;
			++cq,q[cq].id=cq,q[cq].x=rka[e[i].v]-1,q[cq].y=rkb[e[i].u],q[cq].mus=1;
		}
	}
	sort(q+1,q+cq+1,cmpq);
	for(int i=1,j=1;i<=cq;++i)
	{
		for(;j<=(m<<1)&&p[j].x<=q[i].x;++j) insert(p[j].y);
		q[i].res=query(q[i].y);
	}
	sort(q+1,q+cq+1,back);
	long long rX=-m,rY=1ll*m*(m-1)/2;
	for(int i=1;i<=cq;i+=4)
		rX+=(q[i].res+q[i+1].res-q[i+2].res-q[i+3].res)*q[i].mus;
	long long tmp=gcd(rX,rY);rX/=tmp,rY/=tmp;
	printf("%lld/%lld\n",rX,rY);
	return 0;
}