Bzoj3772 精神污染

Posted by yjjr's blog on December 25, 2017

标签:主席树,LCA

题目

题目传送门

Description 兵库县位于日本列岛的中央位置,北临日本海,南面濑户内海直通太平洋,中央部位是森林和山地,与拥有关西机场的大阪府比邻而居,是关西地区面积最大的县,是集经济和文化于一体的一大地区,是日本西部门户,海陆空交通设施发达。濑户内海沿岸气候温暖,多晴天,有日本少见的贸易良港神户港所在的神户市和曾是豪族城邑“城下町”的姬路市等大城市,还有以疗养地而闻名的六甲山地等。 兵库县官方也大力发展旅游,为了方便,他们在县内的N个旅游景点上建立了n-1条观光道,构成了一棵图论中的树。同时他们推出了M条观光线路,每条线路由两个节点x和y指定,经过的旅游景点就是树上x到y的唯一路径上的点。保证一条路径只出现一次。 你和你的朋友打算前往兵库县旅游,但旅行社还没有告知你们最终选择的观光线路是哪一条(假设是线路A)。这时候你得到了一个消息:在兵库北有一群丧心病狂的香菜蜜,他们已经选定了一条观光线路(假设是线路B),对这条路线上的所有景点都释放了【精神污染】。这个计划还有可能影响其他的线路,比如有四个景点1-2-3-4,而【精神污染】的路径是1-4,那么1-3,2-4,1-2等路径也被视为被完全污染了。 现在你想知道的是,假设随便选择两条不同的路径A和B,存在一条路径使得如果这条路径被污染,另一条路径也被污染的概率。换句话说,一条路径被另一条路径包含的概率。

Input 第一行两个整数N,M 接下来N-1行,每行两个数a,b,表示A和B之间有一条观光道。 接下来M行,每行两个数x,y,表示一条旅游线路。

Output 所求的概率,以最简分数形式输出。

Sample Input 5 3

1 2

2 3

3 4

2 5

3 5

2 5

1 4 Sample Output 1/3

样例解释

可以选择的路径对有(1,2),(1,3),(2,3),只有路径1完全覆盖路径2。 HINT

100%的数据满足:N,M<=100000

分析

题意:给定一棵树上M条路径,求任选两条路径时一条被另一条包含的概率是多少

先吐槽毒瘤出题人,真的是精神污染orz

显然,一条路径被另一条路径所包含,那么这条路径的两个端点都在另一条路径上

对于每个节点x,开个vector把另一个端点y存进去

因为主席树是函数式的线段树,相当于前缀和

主席树中每一个节点x都是一个序列,序列的下标表示的是每个节点的入栈序和出栈序,那么将节点x的vector中的y节点入栈序和出栈序在它的序列中分别+1和-1打上标记

假设存在路径x->y,x->z,那么当后者包含前者的时候,y的入栈序一定在z的入栈序和出战序之间

y的出栈序在z的出战序之后,那么可以直接查询z的入出栈序之间的权值和,就是有多少条一端是x节点的路径被x->z所包含

在树上建立主席树,主席树的前缀和就表示从根节点到节点x的路径上序列的和

查询时就相当于查询起点在根节点到x路径上,终点在lca(x,y)与y之间的路径个数

记t为lca(x,y),那么被路径x–>y包含的路径数目就是,$ans=query(in[x])+query(in[y])-query(in[z])-query(in[fa[t]])-1$

这题被卡了几次内存,差评++,毒瘤++

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
const int maxn=1e5+6,maxk=4e6+6;
int ls[maxk],rs[maxk],sum[maxk],n,m,cnt=0,ind,sz;
int last[maxn],deep[maxn],root[200006],in[maxn],out[maxn],fa[maxn][17];
vector<int>a[maxn];
struct query{int x,y;}que[maxn];
struct edge{int to,next;}e[200006];
ll A,B;
bool operator < (query a,query b){return a.x==b.x?a.y<b.y:a.x<b.x;} 
void insert(int u,int v){
	e[++cnt]=(edge){v,last[u]};last[u]=cnt;
	e[++cnt]=(edge){u,last[v]};last[v]=cnt;
}
int insert(int x,int l,int r,int pos,int v){
	int t=++sz,mid=(l+r)>>1;ls[t]=ls[x];rs[t]=rs[x];
	if(l==r){sum[t]=sum[x]+v;return t;}
	if(pos<=mid)ls[t]=insert(ls[t],l,mid,pos,v);else rs[t]=insert(rs[t],mid+1,r,pos,v);
	sum[t]=sum[ls[t]]+sum[rs[t]];return t;
}
int query(int p1,int p2,int p3,int p4,int l,int r,int L,int R){
	int mid=(l+r)>>1;
	if(l==L&&r==R)return sum[p1]+sum[p2]-sum[p3]-sum[p4];
	if(R<=mid)return query(ls[p1],ls[p2],ls[p3],ls[p4],l,mid,L,R);
	else if(L>mid)return query(rs[p1],rs[p2],rs[p3],rs[p4],mid+1,r,L,R);
	else return query(ls[p1],ls[p2],ls[p3],ls[p4],l,mid,L,mid)+query(rs[p1],rs[p2],rs[p3],rs[p4],mid+1,r,mid+1,R);
}
void dfs(int x){
	in[x]=++ind;
	rep(i,1,16)if((1<<i)<=deep[x])fa[x][i]=fa[fa[x][i-1]][i-1];else break;
	reg(x)
		if(e[i].to!=fa[x][0]){
			fa[e[i].to][0]=x;
			deep[e[i].to]=deep[x]+1;
			dfs(e[i].to);
		}
	out[x]=++ind;
}
void dfs2(int x){
	root[x]=root[fa[x][0]];
	for(int i=0;i<a[x].size();i++){
		root[x]=insert(root[x],1,ind,in[a[x][i]],1);
		root[x]=insert(root[x],1,ind,out[a[x][i]],-1);
	}
	reg(x)if(e[i].to!=fa[x][0])dfs2(e[i].to);
}
inline int lca(int x,int y){
	if(deep[x]<deep[y])swap(x,y);
	int t=deep[x]-deep[y];
	rep(i,0,16)if((1<<i)&t)x=fa[x][i];
	dep(i,16,0)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
	if(x==y)return x;else return fa[x][0];
}
void solve(){
	rep(i,1,m){
		int x=que[i].x,y=que[i].y,t=lca(x,y);
		A+=query(root[x],root[y],root[t],root[fa[t][0]],1,ind,in[t],in[x]);
		A+=query(root[x],root[y],root[t],root[fa[t][0]],1,ind,in[t],in[y]);
		A-=query(root[x],root[y],root[t],root[fa[t][0]],1,ind,in[t],in[t]);
		A--;
	}
}
int main()
{
	n=read(),m=read();
	rep(i,1,n-1){
		int u=read(),v=read();insert(u,v);
	}
	rep(i,1,m){
		int x=read(),y=read();a[x].push_back(y);
		que[i].x=x,que[i].y=y;
	}
	sort(que+1,que+1+m);
	dfs(1);dfs2(1);solve();int j;
	for(int i=1;i<=m;i=j)
		for(j=i;que[j].x==que[i].x&&que[j].y==que[i].y;j++)A-=(ll)(j-i)*(j-i-1)/2;
	B=(ll)m*(m-1)/2;
	ll t=gcd(A,B);A/=t,B/=t;
	cout<<A<<'/'<<B<<endl;
	return 0;
}

本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr