Codeforces 1062E 题解

给出一棵有根树，1为根结点，接下来q次询问，每次给出一个[l,r]区间，现在允许删掉[l,r]区间内任何一个点，使得所有点的最近公共祖先的深度尽可能大，问删掉的点是哪个点，深度最大是多少。

做法：

线段树维护区间dfs序的最大值，最小值。

首先，区间的LCA等价于区间dfs序的最小值和最大值对应的两个点的LCA。

然后，根据dfs序的性质，当删掉的点的dfs序最大或者最小时，对答案贡献最大。

所以接下来只要去查询区间里的LCA（最小值，次大值），以及LCA（次小值，最大值），两个LCA中深度最大的就是答案。

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn=1e5+;

 #define ll long long

 int ccnt=;

 int n,cnt,f[maxn],d[maxn],siz[maxn],son[maxn],rk[maxn],top[maxn],tid[maxn];//tid:dfs rk:anti-dfs

 int d_mx;

 struct edge

 {

     int to,next;

 }e[maxn];

 int head[maxn];

 inline void addedge(int u,int v)

 {

     e[++ccnt].to=v;

     e[ccnt].next=head[u];

     head[u]=ccnt;

 }

 void dfs1(int u,int fa,int depth)

 {

     f[u]=fa;

     d[u]=depth;

     d_mx=max(d_mx,d[u]);

     siz[u]=;

     for(int i=head[u]; i ; i=e[i].next)

     {

         int v=e[i].to;

         if(v==fa)

             continue;

         dfs1(v,u,depth+);

         siz[u]+=siz[v];

         if(siz[v]>siz[son[u]])

             son[u]=v;

     }

 }

 void dfs2(int u,int t)

 {

     top[u]=t;

     tid[u]=++cnt;

     rk[cnt]=u;

     if(!son[u])

         return;

     dfs2(son[u],t);

     for(int i=head[u]; i ; i=e[i].next)

     {

         int v=e[i].to;

         if(v!=son[u]&&v!=f[u])

             dfs2(v,v);

     }

 }

 int LCA(int x,int y)

 {

     if(x==y)

         return x;

     int fx=top[x],fy=top[y];

     while(fx!=fy)

     {

         if(d[fx]>=d[fy])

         {

             x=f[fx];

         }

         else

         {

             y=f[fy];

         }

         fx=top[x];

         fy=top[y];

     }

     if(tid[x]<=tid[y]) return x;

     else return y;

 }

 #define lson o*2

 #define rson o*2+1

 #define m (l+r)/2

 struct segment

 {

     int mx,mn;

 }tr[*maxn];

 inline void pushup(int o)

 {

     tr[o].mx=max(tr[lson].mx,tr[rson].mx);

     tr[o].mn=min(tr[lson].mn,tr[rson].mn);

 }

 inline int ret(int o,int flag)

 {

     if(flag) return tr[o].mx;

     else return tr[o].mn;

 }

 void build(int o,int l,int r)

 {

     if(l==r)

     {

         tr[o].mx=tr[o].mn=tid[l];

         return;

     }

     build(lson,l,m);

     build(rson,m+,r);

     pushup(o);

 }

 int query(int o,int l,int r,int ql,int qr,int flag)//1 mx 0 mn

 {

     if(ql>qr)

     {

         if(flag) return ;

         else return maxn;

     }

     if(ql<=l&&qr>=r)

         return ret(o,flag);

     if(qr<=m)

         return query(lson,l,m,ql,qr,flag);

     if(ql>m)

         return query(rson,m+,r,ql,qr,flag);

     if(flag)

         return max(query(lson,l,m,ql,qr,flag),query(rson,m+,r,ql,qr,flag));

     else

         return min(query(lson,l,m,ql,qr,flag),query(rson,m+,r,ql,qr,flag));

 }

 int main()

 {

     int n,q;

     scanf("%d%d",&n,&q);

     for(int i=;i<=n;i++)

     {

         int j;

         scanf("%d",&j);

         addedge(j,i);

     }

     dfs1(,,);

     dfs2(,);

     build(,,n);

     while(q--)

     {

         int l,r;

         scanf("%d%d",&l,&r);

         if(l==r) printf("%d %d\n",l,d_mx);

         int mx=query(,,n,l,r,);

         int mn=query(,,n,l,r,);

         mx=rk[mx];

         mn=rk[mn];

         int cmx=max(query(,,n,l,mx-,),query(,,n,mx+,r,));

         int cmn=min(query(,,n,l,mn-,),query(,,n,mn+,r,));

         cmx=rk[cmx];

         cmn=rk[cmn];

         int lca1=LCA(mx,cmn);

         int lca2=LCA(mn,cmx);

         if(d[lca1]<d[lca2])

             printf("%d %d\n",mx,d[lca2]);

         else

             printf("%d %d\n",mn,d[lca1]);

     }

 }

巴特西

Codeforces 1062E 题解

最新文章

热门文章