Codeforces Round #520 (Div. 2) E. Company(dfs序判断v是否在u的子树里+lca+线段树)

时间:2022-01-02 06:21:00

https://codeforces.com/contest/1062/problem/E

题意

给一颗树n,然后q个询问,询问编号l~r的点,假设可以删除一个点,使得他们的最近公共祖先深度最大。每次询问,输出删除的点和祖先的深度

思路

  • 考虑dfs序来判断v是否在u的子树里:

    dfn[u]<dfn[v]<=max(dfn[u的子树])

  • 那么进一步拓展,dfs序之差越大,点就在越分离的地方,这些点的lca一定是lca(max(dfn[u]),min(dfn[u]))
  • 这不仅知道了需要去掉哪个点(上述两个点之一),而且知道了怎么求点的lca
  • 然后枚举去掉两个点求lca(lca(l,u-1),lca(u+1,r))
  • 线段树维护最小,最大dfn的点
#include<bits/stdc++.h>
#define M 100005
#define pb push_back
#define inf 100000000
using namespace std;
struct N{
int l,r;
array<int,2>mi,ma;
}tr[M<<2];
vector<int>g[M];
int n,q,i,d[M],pre[M],u,v,l,r,a,b,dfn,f[M][30]; void push_up(int o){
tr[o].mi=min(tr[o<<1].mi,tr[o<<1|1].mi);
tr[o].ma=max(tr[o<<1].ma,tr[o<<1|1].ma);
}
int lca(int u,int v){
if(d[v]>d[u])swap(u,v);
int dis=d[u]-d[v];
for(int i=20;i>=0;i--)if(dis&(1<<i))u=f[u][i]; if(u==v)return u; for(int i=20;i>=0;i--)
if(f[u][i]!=f[v][i]){u=f[u][i];v=f[v][i];}
return f[u][0];
} void dfs(int u,int fa){
f[u][0]=fa;for(int i=1;i<=20;i++)f[u][i]=f[f[u][i-1]][i-1];
d[u]=d[fa]+1;pre[u]=++dfn;
//cout<<u<<" "<<d[u]<<endl;
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
dfs(v,u);
}
} void build(int o,int l,int r){
tr[o].l=l;tr[o].r=r;
if(l==r){
tr[o].ma=tr[o].mi={pre[l],l};
return;
}
int mid=(l+r)/2;
build(o<<1,l,mid);
build(o<<1|1,mid+1,r);
push_up(o);
} array<int,2> qy1(int o,int L,int R){
int l=tr[o].l,r=tr[o].r,mid=(l+r)/2;
if(L<=l&&r<=R)return tr[o].mi;
array<int,2>ans={inf,n+1};
if(L<=mid)ans=min(ans,qy1(o<<1,L,R));
if(R>mid)ans=min(ans,qy1(o<<1|1,L,R));
return ans;
}
array<int,2> qy2(int o,int L,int R){
int l=tr[o].l,r=tr[o].r,mid=(l+r)/2;
if(L<=l&&r<=R)return tr[o].ma;
array<int,2>ans={0,n+1};
if(L<=mid)ans=max(ans,qy2(o<<1,L,R));
if(R>mid)ans=max(ans,qy2(o<<1|1,L,R));
return ans;
}
int main(){
dfn=0;
cin>>n>>q;
for(i=2;i<=n;i++){scanf("%d",&u);g[u].pb(i);}
d[0]=-1; dfs(1,0);
build(1,1,n); while(q--){
scanf("%d%d",&l,&r);
u=qy1(1,l,r)[1];v=qy2(1,l,r)[1]; if(u==l)a=lca(qy1(1,l+1,r)[1],qy2(1,l+1,r)[1]);
else if(u==r)a=lca(qy1(1,l,r-1)[1],qy2(1,l,r-1)[1]);
else a=lca(lca(qy1(1,l,u-1)[1],qy2(1,l,u-1)[1]),lca(qy1(1,u+1,r)[1],qy2(1,u+1,r)[1])); if(v==l)b=lca(qy1(1,l+1,r)[1],qy2(1,l+1,r)[1]);
else if(v==r)b=lca(qy1(1,l,r-1)[1],qy2(1,l,r-1)[1]);
else b=lca(lca(qy1(1,l,v-1)[1],qy2(1,l,v-1)[1]),lca(qy1(1,v+1,r)[1],qy2(1,v+1,r)[1]));
//cout<<u<<" "<<a<<endl;
//cout<<v<<" "<<b<<endl;
if(d[a]>d[b])printf("%d %d\n",u,d[a]);
else printf("%d %d\n",v,d[b]);
}
}