题目（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,a%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("%lld/%lld",fenzi,fenmu);
}
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;
}
Comments NOTHING