E. Company
题意
给你一颗具有n个节点的树，有q次查询，每次查询给出l,r
求(l,l+1,l+2…r-1,r)这段区间不考虑哪个节点之后能让剩余节点的lca深度尽量大
做法
这道题有好多种做法，我在做的过程中用了三种做法
首先我们要知道，不考虑一个节点能让一些点的lca发生变化的话，
这个点一定是dfs序最小的点或者dfs序最大的点。
如果能想到这个结论第一种做法就很好想
第一种做法
线段树维护区间lca，st表维护区间dfs序，这样给定一段区间之后
我们就可以通过st表找到哪两个点是dfs最小和最大的点
之后线段树上求该点左侧的区间和该点右侧的区间的lca
对dfs序最小的点求一次，对dfs序最大的点求一次，再取个max就是答案
之后的做法需要知道(猜)另一个结论
一些点的lca就是dfs序最小的点和dfs序最大的点的lca
第二种做法
这样我们用线段树维护区间dfs序，
去掉dfs序最小的点之后在剩下的两个区间查找新的dfs序最小/最大的点
求他们的lca，去掉dfs序最大的点再来一遍，取个max就是答案
第三种做法
第三种做法就是基于第二种做法的基础上，我们直接维护区间最大此大最小次小，这样就可以直接查询当前l,r之内的最大最小最小次小dfs序
删除dfs序最大的点，也就是次大dfs序的点与最小dfs序的点求lca
删除dfs序最小的点，也就是次小dfs序的点与最大dfs序的点求lca
两个取个max即可
代码
第一种做法
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long ll;
#define dbg(x) cout<<#x<<" = "<<x<<endl
#define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl
const int maxn = 1e5+10;
vector<int> G[maxn];
int deep[maxn];
int f[maxn][20];
int in[maxn],mp[maxn],time;
void dfs(int u,int fa)
{
f[u][0]=fa;in[u]=++time;mp[time]=u;for(int i=1; i<=19; i++)f[u][i]=f[f[u][i-1]][i-1];for(int i=0; i<G[u].size(); i++){
int v=G[u][i];if(v==fa)continue;deep[v]=deep[u]+1;dfs(v,u);}
}
int lca(int x,int y)
{
if(x==-1) return y;if(y==-1) return x;if(deep[x]<deep[y]) swap(x,y);for (int i=19; i>=0; i--){
if(deep[x]-(1LL<<i)>=deep[y]) x=f[x][i];}if(x==y) return x;for(int i=19; i>=0; i--)if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];return f[x][0];
}
struct T
{
int l,r,mid;int LCA;
} Tree[maxn<<2];
void push_up(int rt)
{
Tree[rt].LCA=lca(Tree[rt<<1].LCA,Tree[rt<<1|1].LCA);
}
void build(int rt,int l,int r)
{
Tree[rt].l=l;Tree[rt].r=r;Tree[rt].LCA=-1;if(l==r){
Tree[rt].LCA=l;return ;}int mid=Tree[rt].mid=l+r>>1;build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);push_up(rt);
}
int query(int rt,int l,int r)
{
if(l>r) return -1;if(Tree[rt].l>=l&&Tree[rt].r<=r) return Tree[rt].LCA;if(Tree[rt].l>r||Tree[rt].r<l) return -1;int ans=-1;if(l<=Tree[rt].mid) ans=query(rt<<1,l,r);if(r>Tree[rt].mid) ans=lca(ans,query(rt<<1|1,l,r));return ans;
}
inline int min_(int x,int y)
{
return x<y?x:y;
}
inline int max_(int x,int y)
{
return x>y?x:y;
}
int f2[maxn][16],f3[maxn][16];
void build_st(int n)
{
int p=0;for(int i=1; i<=n; i<<=1) p++;for(int i=1; i<=n; i++){
f2[i][0]=in[i];f3[i][0]=in[i];}for(int j=1; j<p; j++){
for(int i=1; i<=n; i++){
if(i+(1<<j-1)>n)f2[i][j]=f2[i][j-1];elsef2[i][j]=max_(f2[i][j-1],f2[i+(1<<j-1)][j-1]);}}for(int j=1; j<p; j++){
for(int i=1; i<=n; i++){
if(i+(1<<j-1)>n) f3[i][j]=f3[i][j-1];else f3[i][j]=min_(f3[i][j-1],f3[i+(1<<j-1)][j-1]);}}
}
int query_max(int l,int r)
{
int p=log2(r-l+1);return max_(f2[l][p],f2[r-(1<<p)+1][p]);
}
int query_min(int l,int r)
{
int p=log2(r-l+1);return min_(f3[l][p],f3[r-(1<<p)+1][p]);
}
int main()
{
int n,q,x,y;scanf("%d%d",&n,&q);for(int i=2; i<=n; i++){
scanf("%d",&x);G[x].push_back(i);G[i].push_back(x);}dfs(1,0);// deep ok lca ok dfsxu okbuild_st(n);build(1,1,n);while(q--){
scanf("%d%d",&x,&y);int st=mp[query_min(x,y)];int en=mp[query_max(x,y)];int ans1=lca(query(1,x,st-1),query(1,st+1,y));int ans2=lca(query(1,x,en-1),query(1,en+1,y));if(deep[ans1]>deep[ans2]) printf("%d %d\n",st,max_(deep[ans1],deep[ans2]));else printf("%d %d\n",en,max_(deep[ans1],deep[ans2]));}return 0;
}
第二种做法
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long ll;
#define dbg(x) cout<<#x<<" = "<<x<<endl
#define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl
const int maxn = 1e5+10;
vector<int> G[maxn];
int deep[maxn];
int f[maxn][20];
int in[maxn],mp[maxn],time;
void dfs(int u,int fa)
{
f[u][0]=fa;in[u]=++time;mp[time]=u;for(int i=1; i<=19; i++)f[u][i]=f[f[u][i-1]][i-1];for(int i=0; i<G[u].size(); i++){
int v=G[u][i];if(v==fa)continue;deep[v]=deep[u]+1;dfs(v,u);}
}
int lca(int x,int y)
{
if(deep[x]<deep[y]) swap(x,y);for (int i=19; i>=0; i--){
if(deep[x]-(1LL<<i)>=deep[y]) x=f[x][i];}if(x==y) return x;for(int i=19; i>=0; i--)if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];return f[x][0];
}
struct T
{
int l,r,mid;int maxx,minn;
} Tree[maxn<<2];
void push_up(int rt)
{
Tree[rt].maxx=max(Tree[rt<<1].maxx,Tree[rt<<1|1].maxx);Tree[rt].minn=min(Tree[rt<<1].minn,Tree[rt<<1|1].minn);
}
void build(int rt,int l,int r)
{
Tree[rt].l=l;Tree[rt].r=r;Tree[rt].maxx=-1;Tree[rt].minn=1000000;if(l==r){
Tree[rt].maxx=in[l];Tree[rt].minn=in[l];return ;}int mid=Tree[rt].mid=l+r>>1;build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);push_up(rt);
}
int ans_max,ans_min;
void query(int rt,int l,int r)
{
if(l>r) return ;if(Tree[rt].l>r||Tree[rt].r<l) return ;if(Tree[rt].l>=l&&Tree[rt].r<=r){
ans_max=max(ans_max,Tree[rt].maxx);ans_min=min(ans_min,Tree[rt].minn);return;}if(l<=Tree[rt].mid) query(rt<<1,l,r);if(r>Tree[rt].mid) query(rt<<1|1,l,r);return ;
}
int main()
{
int n,q,x,y;scanf("%d%d",&n,&q);for(int i=2; i<=n; i++){
scanf("%d",&x);G[x].push_back(i);G[i].push_back(x);}dfs(1,0);build(1,1,n);while(q--){
scanf("%d%d",&x,&y);ans_max=0,ans_min=1000000;query(1,x,y);int st=mp[ans_max];int en=mp[ans_min];ans_max=0,ans_min=1000000;query(1,x,st-1);query(1,st+1,y);int ans1=deep[lca(mp[ans_max],mp[ans_min])];ans_max=0,ans_min=1000000;query(1,x,en-1);query(1,en+1,y);int ans2=deep[lca(mp[ans_max],mp[ans_min])];if(ans1>ans2) printf("%d %d\n",st,ans1);else printf("%d %d\n",en,ans2);}return 0;
}
第三种做法
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long ll;
#define dbg(x) cout<<#x<<" = "<<x<<endl
#define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl
const int maxn = 1e5+10;
vector<int> G[maxn];
int deep[maxn];
int f[maxn][20];
int in[maxn],mp[maxn],time;
void dfs(int u,int fa)
{
f[u][0]=fa;in[u]=++time;mp[time]=u;for(int i=1; i<=19; i++)f[u][i]=f[f[u][i-1]][i-1];for(int i=0; i<G[u].size(); i++){
int v=G[u][i];if(v==fa)continue;deep[v]=deep[u]+1;dfs(v,u);}
}
int lca(int x,int y)
{
if(deep[x]<deep[y]) swap(x,y);for (int i=19; i>=0; i--){
if(deep[x]-(1LL<<i)>=deep[y]) x=f[x][i];}if(x==y) return x;for(int i=19; i>=0; i--)if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];return f[x][0];
}
struct T
{
int l,r,mid;int maxx[2],minn[2];
} Tree[maxn<<2];
void push_up(int rt)
{
vector<int> t;t.push_back(Tree[rt<<1].maxx[0]);t.push_back(Tree[rt<<1].maxx[1]);t.push_back(Tree[rt<<1|1].maxx[0]);t.push_back(Tree[rt<<1|1].maxx[1]);sort(t.begin(),t.end());Tree[rt].maxx[0]=t[3];Tree[rt].maxx[1]=t[2];t.clear();t.push_back(Tree[rt<<1].minn[0]);t.push_back(Tree[rt<<1].minn[1]);t.push_back(Tree[rt<<1|1].minn[0]);t.push_back(Tree[rt<<1|1].minn[1]);sort(t.begin(),t.end());Tree[rt].minn[0]=t[0];Tree[rt].minn[1]=t[1];
}
void build(int rt,int l,int r)
{
Tree[rt].l=l;Tree[rt].r=r;Tree[rt].maxx[0]=-1;Tree[rt].maxx[1]=-1;Tree[rt].minn[0]=1000000;Tree[rt].minn[1]=1000000;if(l==r){
Tree[rt].maxx[0]=in[l];Tree[rt].minn[0]=in[l];return ;}int mid=Tree[rt].mid=l+r>>1;build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);push_up(rt);
}
vector<int> maxx,minn;
bool cmp(int a,int b)
{
return a>b;
}
void query(int rt,int l,int r)
{
if(l>r) return ;if(Tree[rt].l>r||Tree[rt].r<l) return ;if(Tree[rt].l>=l&&Tree[rt].r<=r){
maxx.push_back(Tree[rt].maxx[0]);maxx.push_back(Tree[rt].maxx[1]);minn.push_back(Tree[rt].minn[0]);minn.push_back(Tree[rt].minn[1]);return;}if(l<=Tree[rt].mid) query(rt<<1,l,r);if(r>Tree[rt].mid) query(rt<<1|1,l,r);return ;
}
int main()
{
int n,q,x,y;scanf("%d%d",&n,&q);for(int i=2; i<=n; i++){
scanf("%d",&x);G[x].push_back(i);G[i].push_back(x);}dfs(1,0);build(1,1,n);while(q--){
scanf("%d%d",&x,&y);maxx.clear();minn.clear();query(1,x,y);sort(maxx.begin(),maxx.end(),cmp);sort(minn.begin(),minn.end());int ans1=deep[lca(mp[maxx[0]],mp[minn[1]])];int ans2=deep[lca(mp[maxx[1]],mp[minn[0]])];if(ans1>ans2) printf("%d %d\n",mp[minn[0]],ans1);else printf("%d %d\n",mp[maxx[0]],ans2);}return 0;
}