CF1062E Company

链接

题目大意

给定一颗树，有若干个询问，每个询问给出 l，r，要求编号为 ll~rr 的点任意删去一个之后剩余点的 LCA 深度最大，输出删去点的编号和 LCA 的最大深度

思路

一堆点的lca就是dfs序列的最大和最小的lca

因为只能删除一个点，那就看看删除最大的优秀还是删除最小的优秀。

修改其他的lca是不变的。查询次大线段树麻烦，主席树还能短一点。

代码

#include <bits/stdc++.h>

using namespace std;

const int N=1e5+7;

int read() {

	int x=0,f=1;char s=getchar();

	for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;

	for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';

	return x*f;

}

int n,q,a[N];

vector<int> G[N];

namespace seg {

	struct node {

		int ls,rs,siz,nb;

	}e[N*30];

	int cnt,rt[N];

	void insert(int &rt,int old,int l,int r,int id,int nb) {

		rt=++cnt;

		e[rt]=e[old];

		e[rt].siz++;

		if(l==r) return e[rt].nb=nb,void();

		int mid=(l+r)>>1;

		if(id<=mid) insert(e[rt].ls,e[old].ls,l,mid,id,nb);

		else insert(e[rt].rs,e[old].rs,mid+1,r,id,nb);

	}

	int k_th(int rt,int old,int l,int r,int k) {

		if(l==r) return e[rt].nb;

		int now=e[e[rt].ls].siz-e[e[old].ls].siz;

		int mid=(l+r)>>1;

		if(now>=k) return k_th(e[rt].ls,e[old].ls,l,mid,k);

		else return k_th(e[rt].rs,e[old].rs,mid+1,r,k-now);

	}

}

namespace diss_tree {

	int dep[N],siz[N],fa[N];

	int top[N],son[N],cnt;

	void dfs1(int u,int f) {

        a[u]=++cnt;

		fa[u]=f;

		siz[u]=1;

		for(auto v:G[u]) {

			if(f==v) continue;

            dep[v]=dep[u]+1;

			dfs1(v,u);

			siz[u]+=siz[v];

			if(siz[son[u]]<siz[v]) son[u]=v;

		}

	}

	void dfs2(int u,int topf) {

		top[u]=topf;

		if(!son[u]) return;

		dfs2(son[u],topf);

		for(auto v:G[u])

			if(!top[v]) dfs2(v,v);

	}

	int lca(int x,int y) {

		while(top[x]!=top[y]) {

			if(dep[top[x]]<dep[top[y]]) swap(x,y);

			x=fa[top[x]];

		}

		return dep[x]<dep[y] ? x : y;

	}

}

int main() {

	n=read(),q=read();

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

		int x=read();

		G[x].push_back(i);

		G[i].push_back(x);

	}

	diss_tree::dfs1(1,0);

	diss_tree::dfs2(1,1);

	for(int i=1;i<=n;++i) seg::insert(seg::rt[i],seg::rt[i-1],1,n,a[i],i);

	for(int i=1;i<=q;++i) {

		int x=read(),y=read();

		int first_max=seg::k_th(seg::rt[y],seg::rt[x-1],1,n,1);

		int second_max=seg::k_th(seg::rt[y],seg::rt[x-1],1,n,2);

		int first_min=seg::k_th(seg::rt[y],seg::rt[x-1],1,n,y-x+1);

		int second_min=seg::k_th(seg::rt[y],seg::rt[x-1],1,n,y-x);

		int tmp_x=diss_tree::dep[diss_tree::lca(first_max,second_min)];

		int tmp_y=diss_tree::dep[diss_tree::lca(second_max,first_min)];

		if(tmp_x > tmp_y) printf("%d %d\n",first_min,tmp_x);

		else printf("%d %d\n",first_max,tmp_y);

	}

	return 0;

}

巴特西

CF1062E Company

CF1062E Company

链接

题目大意

思路

代码

最新文章

热门文章