首页 > 其他 > 详细

【JZOJ5918】Car

时间:2018-10-21 22:20:57      阅读:139      评论:0      收藏:0      [点我收藏+]

Description

树上有m条链,Q次询问,每次问一条路径最少被多少条链覆盖。

Solution

还是比较套路的题,求出\(f_{i,j}\)表示\(i\)点经过\(2^j\)条链到达深度最小的点,先考虑\(f_{i,0}\)怎么求,对于一条链,我们在它两个端点处更新\(f_{i,0}\)为它们的\(lca\),然后每个\(f_{i,0}\)都可以被它的儿子更新。
询问时,祖先-后代路径直接倍增跳处理,对于非祖先-后代路径,先把两个端点\(u,v\)跳到不超过\(lca\)的深度最小点\(x,y\),然后有两种情况,一种是\(x\)往上跳到\(lca\)转链下来到\(y\),还有就是一条链直接覆盖\(x,y\)两点。对于第二种情况,我们相当于是要判断一条链的两个端点是否分别在\(x,y\)的子树中。
我们知道,dfs序上子树是连续的,所以这相当与一个二维矩阵内数点的问题,离线扫描线+树状数组可以解决。

Code

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define fo(i,j,k) for(int i=j;i<=k;++i)
#define fd(i,j,k) for(int i=j;i>=k;--i)
#define rep(i,x) for(int i=ls[x];i;i=nx[i])
using namespace std;
const int N=2e5+10,M=4e5+10,T=17;
int to[M],nx[M],ls[N],vl[M],num=0;
void link(int u,int v){
    to[++num]=v,nx[num]=ls[u],ls[u]=num;
}
struct node{
    int x,y,p,t;
}a[M],b[M<<2];
int an[M],cn[M];
int fa[N][T+3],f[N][T+3];
int L[N],R[N],tot=0;
int dep[N];
bool bz[M];
void pre(int x,int fr){
    dep[x]=dep[fr]+1,L[x]=++tot;
    fo(i,1,T) fa[x][i]=fa[fa[x][i-1]][i-1];
    rep(i,x) pre(to[i],x);
    R[x]=tot;
}
void pre2(int x){
    rep(i,x){
        int v=to[i];
        pre2(v);
        if(dep[f[x][0]]>dep[f[v][0]]) f[x][0]=f[v][0];
    }
}
int lca(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    fd(i,T,0) if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
    if(u==v) return u;
    fd(i,T,0) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}
bool cmp(node x,node y){
    return x.x<y.x;
}
int tr[N],n;
void add(int x){
    for(;x<=n;x+=x&-x) tr[x]++;
}
int sum(int x){
    int tmp=0;
    for(;x;x-=x&-x) tmp+=tr[x];
    return tmp;
}
void cr(int x,int y,int p,int t){
    b[++tot].x=x,b[tot].y=y,b[tot].p=p,b[tot].t=t;
}
int main()
{
    freopen("car.in","r",stdin);
    freopen("car.out","w",stdout);
    scanf("%d",&n);
    fo(i,2,n) scanf("%d",&fa[i][0]),link(fa[i][0],i);
    pre(1,0);
    int m;
    scanf("%d",&m);
    fo(i,1,n) f[i][0]=i;
    fo(i,1,m){
        int u,v;
        scanf("%d %d",&u,&v);
        if(L[u]>L[v]) swap(u,v);
        int lc=lca(u,v);
        if(dep[f[u][0]]>dep[lc]) f[u][0]=lc;
        if(dep[f[v][0]]>dep[lc]) f[v][0]=lc;
        a[i].x=L[u],a[i].y=L[v],a[i].t=0;
    }
    pre2(1);
    fo(i,1,n) if(f[i][0]==i) f[i][0]=0;
    fo(j,1,T)
    fo(i,1,n) f[i][j]=f[f[i][j-1]][j-1];
    int q;
    scanf("%d",&q);
    tot=0;
    fo(i,1,q){
        int u,v;
        scanf("%d %d",&u,&v);
        if(u==v) {an[i]=0;continue;}
        if(dep[u]<dep[v]) swap(u,v);
        int lc=lca(u,v),t=0;
        if(lc==v){
            fd(j,T,0) if(dep[f[u][j]]>dep[v]) u=f[u][j],t+=1<<j;
            if(!f[u][0]) {an[i]=-1;continue;}
            an[i]=++t;
            continue;
        }
        fd(j,T,0) if(dep[f[u][j]]>dep[lc]) u=f[u][j],t+=1<<j;
        fd(j,T,0) if(dep[f[v][j]]>dep[lc]) v=f[v][j],t+=1<<j;
        if(!f[u][0] || !f[v][0]) {an[i]=-1;continue;}
        bz[i]=1;
        an[i]=t+1;
        if(L[u]>L[v]) swap(u,v);
        cr(R[u],R[v],i,1);
        cr(L[u]-1,R[v],i,-1);
        cr(R[u],L[v]-1,i,-1);
        cr(L[u]-1,L[v]-1,i,1);
    }
    sort(a+1,a+m+1,cmp),sort(b+1,b+tot+1,cmp);
    int p=0;
    fo(i,1,tot){
        while(p<m && a[p+1].x<=b[i].x) add(a[++p].y);
        cn[b[i].p]+=sum(b[i].y)*b[i].t;
    }
    fo(i,1,q) if(bz[i]) an[i]+=cn[i]==0;
    fo(i,1,q) printf("%d\n",an[i]);
}

【JZOJ5918】Car

原文:https://www.cnblogs.com/sadstone/p/9827274.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!