文件详细信息

下载本文件

本文件的大小为 4327 字节。

#include<algorithm>
#include<cstdio>
#include<tuple>
#include<vector>
namespace IO{
	const int ARR_SIZE=1<<20;
	#define gc() ((IO::si!=IO::ti||(IO::ti=(IO::si=IO::input)+fread(IO::input,1,IO::ARR_SIZE,stdin))),IO::si!=IO::ti?*(IO::si++):EOF)
	#define pc(ch) ((IO::o.so!=IO::o.to||(fwrite(IO::o.output,1,IO::ARR_SIZE,stdout),IO::o.so=IO::o.output)),*(IO::o.so++)=ch)
	char input[ARR_SIZE],*si=input,*ti=input;
	struct Output_Stream{
		char output[ARR_SIZE],*so=output,*to=output+ARR_SIZE;
		~Output_Stream(){
			if(so==output)return;
			fwrite(output,1,so-output,stdout);
			so=output;
		}
	}o;
	template<typename T>
	void read(T&num){
		int ch=gc();
		num=0;
		while(ch<48||ch>57)ch=gc();
		while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=gc();
	}
	template<typename T>
	void write(T a){
		static int ch[50],cnt=0;
		if(a==0)pc('0');
		while(a)ch[++cnt]=a%10|48,a/=10;
		while(cnt)pc(ch[cnt--]);
	}
}
using IO::read;
using IO::write;
const int inf=0x3f3f3f3f;
typedef std::pair<int,int>pii;
typedef std::tuple<int,int,int>tiii;
template<typename T>
inline void chkmax(T&a,const T&b){
	if(a<b)a=b;
}
template<typename T>
inline void chkmin(T&a,const T&b){
	if(a>b)a=b;
}
struct set2{
	pii mn1,mn2;
	set2():mn1(inf,0),mn2(inf,0){}
	void insert(const pii&x){
		if(mn1>x)mn2=mn1,mn1=x;
		else if(mn2>x)mn2=x;
	}
};
const int maxn=200000,maxm=200000,maxlog2n=31-__builtin_clz(maxn);
int n,m,fa[maxn+1],dep[maxn+1],mn[maxlog2n+1][maxn+1];
int dfn[maxn+1],vis_cnt;
std::vector<int>g[maxn+1];
set2 st[maxn+1];
std::vector<pii>ins[maxn+1];
tiii pth[maxm+1],ans(0,1,2);
bool cmp(const int u,const int v){
	return dep[u]<dep[v];
}
void dfs_init(const int u){
	dep[u]=dep[fa[u]]+1;
	dfn[u]=++vis_cnt;
	mn[0][vis_cnt]=fa[u];
	for(const int v:g[u])dfs_init(v);
}
void lca_init(){
	for(int i=1;(1<<i)<=n;i++)
		for(int j=1,inc=1<<(i-1),lim=n-(1<<i)+1;j<=lim;j++)
			mn[i][j]=std::min(mn[i-1][j],mn[i-1][j+inc],cmp);
}
int lca(int u,int v){
	if(u==v)return u;
	u=dfn[u],v=dfn[v];
	if(u>v)std::swap(u,v);
	const int k=31-__builtin_clz(v-u++);
	return std::min(mn[k][u],mn[k][v-(1<<k)+1],cmp);
}
void upd(const int x,const int y){
	if(x==y)return;
	int u1,v1,t1,u2,v2,t2;
	std::tie(u1,v1,t1)=pth[x];
	std::tie(u2,v2,t2)=pth[y];
	int mx1=lca(u1,v2),mx2=lca(u1,u2);
	if(dep[mx1]<dep[mx2])std::swap(mx1,mx2);
	auto work=[&](const int u){
		if(dep[mx1]<dep[u])mx2=mx1,mx1=u;
		else if(dep[mx2]<dep[u])mx2=u;
	};
	work(lca(v1,u2));
	work(lca(v1,v2));
	chkmax(ans,tiii(dep[mx1]+dep[mx2]-dep[lca(mx1,mx2)]*2,x,y));
}
namespace sgt{
	struct node{
		node*ls,*rs;
		int lft,rgt;
	}tr[maxm*2*(maxlog2n+1)+1],*tot=tr;
	void pushup(node*u){
		u->lft=u->ls?u->ls->lft:u->rs->lft;
		u->rgt=u->rs?u->rs->rgt:u->ls->rgt;
	}
	node*update(node*u,const int l,const int r,const int pos,const int val,const int lst,const int nxt){
		if(!u)u=tot++;
		if(l==r){
			if(u->lft)upd(val,u->lft);
			else{
				u->lft=u->rgt=val;
				if(lst)upd(val,lst);
				if(nxt)upd(val,nxt);
			}
		}else{
			const int mid=(l+r)>>1;
			if(pos<=mid)u->ls=update(u->ls,l,mid,pos,val,lst,u->rs?u->rs->lft:nxt);
			else u->rs=update(u->rs,mid+1,r,pos,val,u->ls?u->ls->rgt:lst,nxt);
			pushup(u);
		}
		return u;
	}
	node*merge(node*u,node*v,const int l,const int r){
		if(!u)return v;
		if(!v)return u;
		if(l==r)upd(u->lft,v->lft);
		else{
			const int mid=(l+r)>>1;
			u->ls=merge(u->ls,v->ls,l,mid);
			u->rs=merge(u->rs,v->rs,mid+1,r);
			if(u->ls&&u->rs)upd(u->ls->rgt,u->rs->lft);
			pushup(u);
		}
		return u;
	}
}
sgt::node*rt[maxn+1];
void dfs(const int u){
	for(const int v:g[u]){
		dfs(v);
		st[u].insert(st[v].mn1);
		st[u].insert(st[v].mn2);
		rt[u]=sgt::merge(rt[u],rt[v],1,n);
	}
	for(const pii&i:ins[u])rt[u]=sgt::update(rt[u],1,n,i.first,i.second,0,0);
	if(st[u].mn1.first<dep[u]&&st[u].mn2.first<dep[u])chkmax(ans,tiii(dep[u]-std::max(st[u].mn1.first,st[u].mn2.first),st[u].mn1.second,st[u].mn2.second));
}
int main(){
	read(n),read(m);
	for(int i=2;i<=n;i++){
		read(fa[i]);
		g[fa[i]].emplace_back(i);
	}
	dfs_init(1);
	lca_init();
	for(int i=1,u,v,t;i<=m;i++){
		read(u),read(v);
		t=lca(u,v);
		st[u].insert({dep[t],i});
		st[v].insert({dep[t],i});
		ins[u].emplace_back(dfn[v],i);
		ins[v].emplace_back(dfn[u],i);
		pth[i]=tiii(u,v,t);
	}
	dfs(1);
	write(std::get<0>(ans)),pc('\n');
	write(std::get<1>(ans)),pc(' '),write(std::get<2>(ans)),pc('\n');
	return 0;
}