「BZOJ3772」精神污染

2015年1月27日6,2790

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

题解

参见http://blog.csdn.net/popoqqq/article/details/43122821

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#define eps 1e-8
#define inf 1000000000
#define pa pair<int,int>
#define ll long long 
using namespace std;
int read()
{
    int x=0,f=1;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;
}
ll gcd(ll a,ll b)
{
	return b==0?a:gcd(b,a%b);
}
ll A,B;
int ls[4000005],rs[4000005],sum[4000005];
int bin[20];
int n,m,cnt,ind,size;
int last[100005],deep[100005],root[200005],in[100005],out[100005];
int fa[100005][17];
vector<int> a[100005];
struct query{
	int x,y;
}q[100005];
bool operator<(query a,query b)
{
	if(a.x==b.x)return a.y<b.y;
	else return a.x<b.x;
}
struct edge{
	int to,next;
}e[200005];
void insert(int u,int v)
{
	e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
	e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;
}
int insert(int x,int l,int r,int pos,int val)
{
	int t=++size;
	ls[t]=ls[x];rs[t]=rs[x];
	if(l==r){sum[t]=sum[x]+val;return t;}
	int mid=(l+r)>>1;
	if(pos<=mid)ls[t]=insert(ls[t],l,mid,pos,val);
	else rs[t]=insert(rs[t],mid+1,r,pos,val);
	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 st,int ed)
{
	int mid=(l+r)>>1;
	if(l==st&&r==ed)
	{
		return sum[p1]+sum[p2]-sum[p3]-sum[p4];
	}
	if(ed<=mid)return query(ls[p1],ls[p2],ls[p3],ls[p4],l,mid,st,ed);
	else if(st>mid)return query(rs[p1],rs[p2],rs[p3],rs[p4],mid+1,r,st,ed);
	else 
		return query(ls[p1],ls[p2],ls[p3],ls[p4],l,mid,st,mid)+query(rs[p1],rs[p2],rs[p3],rs[p4],mid+1,r,mid+1,ed);
}
void dfs(int x)
{
	in[x]=++ind;
	for(int i=1;bin[i]<=deep[x];i++)
		fa[x][i]=fa[fa[x][i-1]][i-1];
	for(int i=last[x];i;i=e[i].next)
		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);
	}
	for(int i=last[x];i;i=e[i].next)
		if(e[i].to!=fa[x][0])
			dfs2(e[i].to);
}
int lca(int x,int y)
{
	if(deep[x]<deep[y])swap(x,y);
	int t=deep[x]-deep[y];
	for(int i=0;i<=16;i++)
		if(t&bin[i])
			x=fa[x][i];
	for(int i=16;i>=0;i--)
		if(fa[x][i]!=fa[y][i])
			x=fa[x][i],y=fa[y][i];
	if(x==y)return x;
	return fa[x][0];
}
void solve()
{
	for(int i=1;i<=m;i++)
	{
		int x=q[i].x,y=q[i].y,f=lca(x,y);
		A+=query(root[x],root[y],root[f],root[fa[f][0]],1,ind,in[f],in[x]);
		A+=query(root[x],root[y],root[f],root[fa[f][0]],1,ind,in[f],in[y]);
		A-=query(root[x],root[y],root[f],root[fa[f][0]],1,ind,in[f],in[f]);
		A--;
	}
}
int main()
{
	bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1;
	n=read();m=read();
	for(int i=1;i<n;i++)
	{
		int u=read(),v=read();
		insert(u,v);
	}
	for(int i=1;i<=m;i++)
	{
		int x=read(),y=read();
		a[x].push_back(y);
		q[i].x=x,q[i].y=y;
	}
	sort(q+1,q+m+1);
	dfs(1);
	dfs2(1);
	solve();
	int j;
	for(int i=1;i<=m;i=j)
		for(j=i;q[j].x==q[i].x&&q[j].y==q[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;
	printf("%lld/%lld",A,B);
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<vector>

#include<queue>

#include<algorithm>

#include<map>

#include<cmath>

#define eps 1e-8

#define inf 1000000000

#define pa pair<int,int>

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;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;

}

ll gcd(ll a,ll b)

{

return b==0?a:gcd(b,a%b);

}

ll A,B;

int ls[4000005],rs[4000005],sum[4000005];

int bin[20];

int n,m,cnt,ind,size;

int last[100005],deep[100005],root[200005],in[100005],out[100005];

int fa[100005][17];

vector<int> a[100005];

struct query{

int x,y;

}q[100005];

bool operator<(query a,query b)

{

if(a.x==b.x)return a.y<b.y;

else return a.x<b.x;

}

struct edge{

int to,next;

}e[200005];

void insert(int u,int v)

{

e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;

e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;

}

int insert(int x,int l,int r,int pos,int val)

{

int t=++size;

ls[t]=ls[x];rs[t]=rs[x];

if(l==r){sum[t]=sum[x]+val;return t;}

int mid=(l+r)>>1;

if(pos<=mid)ls[t]=insert(ls[t],l,mid,pos,val);

else rs[t]=insert(rs[t],mid+1,r,pos,val);

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 st,int ed)

{

int mid=(l+r)>>1;

if(l==st&&r==ed)

{

return sum[p1]+sum[p2]-sum[p3]-sum[p4];

}

if(ed<=mid)return query(ls[p1],ls[p2],ls[p3],ls[p4],l,mid,st,ed);

else if(st>mid)return query(rs[p1],rs[p2],rs[p3],rs[p4],mid+1,r,st,ed);

else

return query(ls[p1],ls[p2],ls[p3],ls[p4],l,mid,st,mid)+query(rs[p1],rs[p2],rs[p3],rs[p4],mid+1,r,mid+1,ed);

}

void dfs(int x)

{

in[x]=++ind;

for(int i=1;bin[i]<=deep[x];i++)

fa[x][i]=fa[fa[x][i-1]][i-1];

for(int i=last[x];i;i=e[i].next)

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);

}

for(int i=last[x];i;i=e[i].next)

if(e[i].to!=fa[x][0])

dfs2(e[i].to);

}

int lca(int x,int y)

{

if(deep[x]<deep[y])swap(x,y);

int t=deep[x]-deep[y];

for(int i=0;i<=16;i++)

if(t&bin[i])

x=fa[x][i];

for(int i=16;i>=0;i--)

if(fa[x][i]!=fa[y][i])

x=fa[x][i],y=fa[y][i];

if(x==y)return x;

return fa[x][0];

}

void solve()

{

for(int i=1;i<=m;i++)

{

int x=q[i].x,y=q[i].y,f=lca(x,y);

A+=query(root[x],root[y],root[f],root[fa[f][0]],1,ind,in[f],in[x]);

A+=query(root[x],root[y],root[f],root[fa[f][0]],1,ind,in[f],in[y]);

A-=query(root[x],root[y],root[f],root[fa[f][0]],1,ind,in[f],in[f]);

A--;

}

int main()

{

bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1;

n=read();m=read();

for(int i=1;i<n;i++)

{

int u=read(),v=read();

insert(u,v);

}

for(int i=1;i<=m;i++)

{

int x=read(),y=read();

a[x].push_back(y);

q[i].x=x,q[i].y=y;

}

sort(q+1,q+m+1);

dfs(1);

dfs2(1);

solve();

int j;

for(int i=1;i<=m;i=j)

for(j=i;q[j].x==q[i].x&&q[j].y==q[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;

printf("%lld/%lld",A,B);

return 0;

}

« 「BZOJ3611」[HEOI2014] 大工程「fjWC2015」当小威遇上经济危机 »

Mychael

请教一下黄学长，146~148行那两个循环意义何在？【似乎删掉也可以A】

hzwer.com _ Home | http://hzwer.com

「BZOJ3772」精神污染

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论