[bzoj3772]-精神污染

发布于 2018-02-26  27 次阅读



题目(BZOJ) *权限
 
来说说这题吧~
对于一条路径,我们可以将其分成两条:x->lca,y->lca。
若A路径包含B路径,则B路径的两端点必然在A路径上,
所以我们可以开个vector:若一条路径x->y,则a[x].push_back(y),
这样,问题就简单了:
直接求a[x]里面在某条路径上的点的个数即可,而这个明显可以用主席树解决。

#include <cstdio>
#include <algorithm>
#include <cctype>
#include <vector>
using namespace std;
typedef long long ll;
template <class _E> inline void read(_E &e){
	e=0;bool ck=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
	while(isdigit(ch)){e=(e<<1)+(e<<3)+(ch^48);ch=getchar();}
	if(ck)e=-e;
}
const int N=100001;
int n,m;
ll gcd(ll a,ll b){return b==0?a:gcd(b,
ll fenzi,fenmu;
struct routes{
	int x,y;
}q[N];
inline bool cmp(const routes &x,const routes &y){
	if(x.x==y.x)return x.y<y.y;
	else return x.x<y.x;
}
vector <int> g[N],a[N];
inline void ad(int u,int v){g[u].push_back(v);g[v].push_back(u);}
int dep[N],p[N][17],in[N],out[N],idx;
void dfslca(int u){
	in[u]=++idx;
	for(int i=1;i<=16;++i)p[u][i]=p[p[u][i-1]][i-1];
	for(int i=0;i<g[u].size();++i){
		int v=g[u][i];
		if(v==p[u][0])continue;
		dep[v]=dep[u]+1;
		p[v][0]=u;
		dfslca(v);
	}
	out[u]=++idx;
}
inline int lca(int x,int y){
	if(dep[y]<dep[x])swap(x,y);
	for(int i=16;i>=0;--i){
		if(dep[y]-(1<<i)<dep[x])continue;
		y=p[y][i];
	}
	if(x==y)return y;
	for(int i=16;i>=0;--i){
		if(p[x][i]==p[y][i])continue;
		x=p[x][i];y=p[y][i];
	}
	return p[y][0];
}
int ls[4000001],rs[4000001],s[4000001],rt[200001],tsz;
inline void pushup(int x){s[x]=s[ls[x]]+s[rs[x]];}
int insert(int l,int r,int x,int pos,int v){
	int t=++tsz;ls[t]=ls[x],rs[t]=rs[x];
	if(l==r){s[t]=s[x]+v;return t;}
	int mid=(l+r)>>1;
	if(pos<=mid)ls[t]=insert(l,mid,ls[t],pos,v);
	else rs[t]=insert(mid+1,r,rs[t],pos,v);
	pushup(t);
	return t;
}
int query(int l,int r,int p1,int p2,int p3,int p4,int L,int R){
	if(l==L&&r==R){return s[p1]+s[p2]-s[p3]-s[p4];}
	int mid=(l+r)>>1;
	if(R<=mid)return query(l,mid,ls[p1],ls[p2],ls[p3],ls[p4],L,R);
	else if(L>mid)return query(mid+1,r,rs[p1],rs[p2],rs[p3],rs[p4],L,R);
	else return query(l,mid,ls[p1],ls[p2],ls[p3],ls[p4],L,mid)+query(mid+1,r,rs[p1],rs[p2],rs[p3],rs[p4],mid+1,R);
}
void build(int u){
	rt[u]=rt[p[u][0]];
	for(int i=0;i<a[u].size();++i){
		rt[u]=insert(1,idx,rt[u],in[a[u][i]],1);
		rt[u]=insert(1,idx,rt[u],out[a[u][i]],-1);
	}
	for(int i=0;i<g[u].size();++i){
		if(g[u][i]==p[u][0])continue;
		build(g[u][i]);
	}
}
void solve(){
	for(int i=1;i<=m;++i){
		int l=lca(q[i].x,q[i].y);
		fenzi+=query(1,idx,rt[q[i].x],rt[q[i].y],rt[l],rt[p[l][0]],in[l],in[q[i].x]);
		fenzi+=query(1,idx,rt[q[i].x],rt[q[i].y],rt[l],rt[p[l][0]],in[l],in[q[i].y]);
		fenzi-=query(1,idx,rt[q[i].x],rt[q[i].y],rt[l],rt[p[l][0]],in[l],in[l]);
		fenzi--;
	}
	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++)
			fenzi-=(ll)(j-i)*(j-i-1)/2;
	ll gc=gcd(fenzi,fenmu);
	fenzi/=gc,fenmu/=gc;
	printf(
}
int main(){
	read(n),read(m);
	fenmu=(ll)m*(m-1)/2;
	for(int i=1;i<n;++i){int u,v;read(u),read(v);ad(u,v);}
	dfslca(1);
	for(int i=1;i<=m;++i){
		read(q[i].x),read(q[i].y);
		a[q[i].x].push_back(q[i].y);
	}
	sort(q+1,q+m+1,cmp);
	build(1);
	solve();
	return 0;
}