传送门-->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便为所有二维点被几个矩形包含的和减去的二维点个数（因为同时有同一条路径构出的矩形和二维点），扫描线即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | #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 100010int 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...
评论 (0)
