本文主要是介绍Codeforces Contest 1062 problem E Company —— lca+主席树+dfs序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
The company X has n employees numbered from 1 through n. Each employee u has a direct boss pu (1≤pu≤n), except for the employee 1 who has no boss. It is guaranteed, that values pi form a tree. Employee u is said to be in charge of employee v if u is the direct boss of v or there is an employee w such that w is in charge of v and u is the direct boss of w. Also, any employee is considered to be in charge of himself.
In addition, for each employee u we define it’s level lv(u) as follow:
lv(1)=0
lv(u)=lv(pu)+1 for u≠1
In the near future, there are q possible plans for the company to operate. The i-th plan consists of two integers li and ri, meaning that all the employees in the range [li,ri], and only they, are involved in this plan. To operate the plan smoothly, there must be a project manager who is an employee in charge of all the involved employees. To be precise, if an employee u is chosen as the project manager for the i-th plan then for every employee v∈[li,ri], u must be in charge of v. Note, that u is not necessary in the range [li,ri]. Also, u is always chosen in such a way that lv(u) is as large as possible (the higher the level is, the lower the salary that the company has to pay the employee).
Before any plan is operated, the company has JATC take a look at their plans. After a glance, he tells the company that for every plan, it’s possible to reduce the number of the involved employees exactly by one without affecting the plan. Being greedy, the company asks JATC which employee they should kick out of the plan so that the level of the project manager required is as large as possible. JATC has already figured out the answer and challenges you to do the same.
Input
The first line contains two integers n and q (2≤n≤100000, 1≤q≤100000) — the number of employees and the number of plans, respectively.
The second line contains n−1 integers p2,p3,…,pn (1≤pi≤n) meaning pi is the direct boss of employee i.
It is guaranteed, that values pi form a directed tree with the root of 1.
Each of the following q lines contains two integers li and ri (1≤li<ri≤n) — the range of the employees, involved in the corresponding plan.
Output
Print q lines, each containing two integers — the number of the employee which should be kicked from the corresponding plan and the maximum possible level of the project manager in that case.
If there are more than one way to choose that employee, print any of them.
Example
inputCopy
11 5
1 1 3 3 3 4 2 7 7 6
4 6
4 8
1 11
9 11
8 11
outputCopy
4 1
8 1
1 0
11 3
8 1
Note
In the example:
In the first query, we can choose whether 4 or 5 or 6 and the project manager will be 3.
In the second query, if we choose any employee other than the employee 8, the project manager will be 1. If we choose 8, the project manager will be 3. Since lv(3)=1>lv(1)=0, choosing 8 is the best strategy.
In the third query, no matter how we choose the employee, the project manager will always be 1.
In the fourth query, if we choose 9 or 10 then the project manager will be 3. If we choose 11 then the project manager will be 7. Since lv(7)=3>lv(3)=1, we choose 11 as the answer.
题意：
给你2-n的父亲，每一个节点的值就是它的深度，给你m个区间，让你去掉一个数，使得所有节点的lca深度最大。
题解：
最大lca肯定是两个最远点去掉一个，那我们就dfs标记每一个节点，用主席树两个最远的点和两个次远的点，由于在同一个节点下不需要考虑顺序的问题，那么就算它的节点标记是123或者321都无所谓。找到之后我们只需要看删掉哪一个最远点就好了
#include<bits/stdc++.h>
using namespace std;
#define N 100005
int head[N],fa[N][25],vis[N],cnt,dep[N],lv[N];
struct node
{int to,next;
}e[N<<1];
void add(int x,int y)
{e[cnt].to=y;e[cnt].next=head[x];head[x]=cnt++;
}
//lca所属
void bfs()
{fa[1][0]=1;dep[1]=0;queue<int>Q;Q.push(1);while(!Q.empty()){int u,v;u=Q.front();Q.pop();for(int i=1;i<=16;i++)fa[u][i]=fa[fa[u][i-1]][i-1];for(int i=head[u];~i;i=e[i].next){v=e[i].to;if(v==fa[u][0])continue;dep[v]=dep[u]+1;fa[v][0]=u;Q.push(v);}}
}
int lca(int x,int y){if(dep[x]<dep[y])swap(x,y);
//令x为深度较深的点for(int i=16;i>=0;i--)if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
//让x向上走到与y同一深度if(x==y)return x; //如果直接是lca，直接返回for(int i=16;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
//x，y同时向上走，直到父节点相同return fa[x][0]; //返回父节点
}
int dfn[N],anti[N];
int number;
//确定节点远近所属
void dfs(int x)
{dfn[x]=++number;anti[number]=x;for(int i=head[x];~i;i=e[i].next){int ne=e[i].to;lv[ne]=lv[x]+1;dfs(ne);}
}
//主席树所属
int num[N*30],ls[N*30],rs[N*30],rt[N],tot;
void update(int l,int r,int root,int last,int pos)
{ls[root]=ls[last];rs[root]=rs[last];num[root]=num[last]+1;if(l==r)return ;int mid=l+r>>1;if(mid>=pos)update(l,mid,ls[root]=++tot,ls[last],pos);elseupdate(mid+1,r,rs[root]=++tot,rs[last],pos);
}
int qmax(int l,int r,int root,int last)
{if(l==r)return l;int sum=num[rs[root]]-num[rs[last]];int mid=l+r>>1;if(sum>=1)return qmax(mid+1,r,rs[root],rs[last]);elsereturn qmax(l,mid,ls[root],ls[last]);
}
int qsecmax(int l,int r,int root,int last,int val)
{if(l==r)return l;int sum=num[rs[root]]-num[rs[last]];int mid=l+r>>1;if(sum>=val)return qsecmax(mid+1,r,rs[root],rs[last],val);elsereturn qsecmax(l,mid,ls[root],ls[last],val-sum);
}
int qmin(int l,int r,int root,int last)
{if(l==r)return l;int sum=num[ls[root]]-num[ls[last]];int mid=l+r>>1;if(sum>=1)return qmin(l,mid,ls[root],ls[last]);elsereturn qmin(mid+1,r,rs[root],rs[last]);
}
int qsecmin(int l,int r,int root,int last,int val)
{if(l==r)return l;int sum=num[ls[root]]-num[ls[last]];int mid=l+r>>1;if(sum>=val)return qsecmin(l,mid,ls[root],ls[last],val);elsereturn qsecmin(mid+1,r,rs[root],rs[last],val-sum);
}
int main()
{memset(head,-1,sizeof(head));int n,m;scanf("%d%d",&n,&m);int x;for(int i=2;i<=n;i++){scanf("%d",&x);add(x,i);}bfs(),dfs(1);for(int i=1;i<=n;i++)update(1,n,rt[i]=++tot,rt[i-1],dfn[i]);int l,r;for(int i=1;i<=m;i++){scanf("%d%d",&l,&r);int maxn=anti[qmax(1,n,rt[r],rt[l-1])];int secmaxn=anti[qsecmax(1,n,rt[r],rt[l-1],2)];int minn=anti[qmin(1,n,rt[r],rt[l-1])];int secminn=anti[qsecmin(1,n,rt[r],rt[l-1],2)];int l1=lca(secmaxn,minn),l2=lca(secminn,maxn);if(lv[l1]>=lv[l2])printf("%d %d\n",maxn,lv[l1]);elseprintf("%d %d\n",minn,lv[l2]);}return 0;
}这篇关于Codeforces Contest 1062 problem E Company —— lca+主席树+dfs序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
