cf983E NN Country (倍增+dfs序+树状数组)

首先可以求出从某点做$2^k$次车能到的最浅的点,这个只要dfs一下,把它的孩子能到的最浅的点更新过来就可以

然后倍增地往上跳,不能跳到lca的上面,记录坐车的次数ans

此时有三种情况(设最远能跳到x,y):

  1.再跳也跳不到lca的上面,就是-1

  2.路径(x,y)被某趟车覆盖,答案是ans+1

  3.并没有被覆盖,答案是ans+2

那么怎么看有没有覆盖呢

首先,如果这两个点是直上直下的(有一个是lca),只要看下面那个点能不能跳到上面去就行

对于剩下的(x,y),只要有车的两端点分别在x和y的子树中就可以

所以做一遍dfs,进某个点x的时候记下来y的子树中车端点的个数,然后把从x发的车的终点++,出来的时候再次统计那个个数,如果不相同,就说明(x,y)这条路径被覆盖了。这个在dfs序上用一个树状数组就可以

不要把N写成M然后WA一页,很难看。

 #include<bits/stdc++.h>
#define pa pair<int,int>
#define CLR(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=2e5+; inline ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} int eg[maxn][],egh[maxn],ect;
int N,M,Q,dep[maxn],fa[maxn][],nxt[maxn][];
int dfn[maxn][],tot,ans[maxn];
int pt[maxn*][],pth[maxn],tr[maxn];
int lq[maxn*][],lqh[maxn],tmp[maxn*];
bool covered[maxn]; inline void adeg(int a,int b){
eg[++ect][]=b,eg[ect][]=egh[a],egh[a]=ect;
} void dfs(int x){
dfn[x][]=++tot;
for(int i=;fa[x][i]&&fa[fa[x][i]][i];i++)
fa[x][i+]=fa[fa[x][i]][i];
for(int i=egh[x];i;i=eg[i][]){
int b=eg[i][];
dep[b]=dep[x]+;
dfs(b);
}dfn[x][]=tot;
} int getlca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
for(int i=;i>=&&dep[x]!=dep[y];i--){
if(fa[x][i]&&dep[fa[x][i]]>=dep[y])
x=fa[x][i];
}
if(x==y) return x;
for(int i=;i>=;i--){
if(fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
}
return fa[x][];
} void dfs2(int x){
for(int i=egh[x];i;i=eg[i][]){
int b=eg[i][];
dfs2(b);
if(nxt[b][]&&(dep[nxt[b][]]<dep[nxt[x][]]||!nxt[x][]))
nxt[x][]=nxt[b][];
}
if(dep[nxt[x][]]>=dep[x]) nxt[x][]=;
} inline int lowbit(int x){return x&(-x);}
inline void add(int x,int y){
for(;x<=N;x+=lowbit(x)) tr[x]+=y;
}
inline int query(int x){
int re=;for(;x;x-=lowbit(x)) re+=tr[x];return re;
} void dfs3(int x){
for(int i=lqh[x];i;i=lq[i][]){
int b=lq[i][];
tmp[i]=query(dfn[b][])-query(dfn[b][]-);
}
for(int i=pth[x];i;i=pt[i][]){
int b=pt[i][];
add(dfn[b][],);
}
for(int i=egh[x];i;i=eg[i][]){
int b=eg[i][];
dfs3(b);
}
for(int i=lqh[x];i;i=lq[i][]){
int b=lq[i][];
if(tmp[i]!=query(dfn[b][])-query(dfn[b][]-))
covered[i>>]=;
}
} int main(){
// freopen("983E.in","r",stdin);
int i,j,k;
N=rd();
for(i=;i<=N;i++){
fa[i][]=rd();
adeg(fa[i][],i);
}
dep[]=;dfs();
M=rd();
for(i=;i<=M;i++){
int a=rd(),b=rd();
pt[i<<][]=a,pt[i<<][]=pth[b],pth[b]=i<<;
pt[i<<|][]=b,pt[i<<|][]=pth[a],pth[a]=i<<|;
int x=getlca(a,b);
if(dep[x]<dep[nxt[a][]]||!nxt[a][]) nxt[a][]=x;
if(dep[x]<dep[nxt[b][]]||!nxt[b][]) nxt[b][]=x;
}
dfs2();
for(i=;i<;i++){
for(j=;j<=N;j++){
// if(!nxt[j][i]||!nxt[nxt[j][i]][i]) continue;
nxt[j][i+]=nxt[nxt[j][i]][i];
}
}
Q=rd();
for(i=;i<=Q;i++){
int a=rd(),b=rd(),lca=getlca(a,b);
for(j=;j>=;j--){
if(nxt[a][j]&&dep[nxt[a][j]]>dep[lca])
ans[i]+=<<j,a=nxt[a][j];
}
for(j=;j>=;j--){
if(nxt[b][j]&&dep[nxt[b][j]]>dep[lca])
ans[i]+=<<j,b=nxt[b][j];
}
if((a==lca&&nxt[b][]&&dep[nxt[b][]]<=dep[lca])||(b==lca&&nxt[a][]&&dep[nxt[a][]]<=dep[lca]))
ans[i]+=;
else if(nxt[a][]&&nxt[b][]&&dep[nxt[a][]]<=dep[lca]&&dep[nxt[b][]]<=dep[lca]){
ans[i]+=;
lq[i<<][]=a,lq[i<<][]=lqh[b],lqh[b]=i<<;
lq[i<<|][]=b,lq[i<<|][]=lqh[a],lqh[a]=i<<|;
}else{
ans[i]=-;
}
}
dfs3();
for(i=;i<=Q;i++)
printf("%d\n",ans[i]-covered[i]);
return ;
}
上一篇:NC 5的开发环境起不了客户端


下一篇:MVVM以及vue的双向绑定