100分LCA求调玄关
查看原帖
100分LCA求调玄关
922019
xiaoniu142857楼主2024/10/4 15:00
#include <cstdio>
#include <algorithm>
#define N 100001
#define K 18
#define rep(i,a,b) for(register int i(a);i<(b);++i)
#define repg(i,x) for(register int i(hd[x]);i;i=nxt[i])
#define add(x,y) (to[++cnt]=y,nxt[cnt]=hd[x],hd[x]=cnt)
using namespace std;
int rt[N][K],high[N],log[N],dep[N],hd[N],to[N],nxt[N],cnt;
template<typename T>
inline void read(T &x)
{
    int c;
    while((c=getchar())<'0'||c>'9');
    for(x=c^48;(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+(c^48));
}
template<typename T>
inline void write(T x)
{
    if(x<10) putchar(x|48);
    else write(x/10),putchar(x%10|48);
}
void init_log()
{
	log[0]=-1;
	for(int i(1);i<N;++i)
	{
		log[i]=log[i>>1]+1;
	}
}
void init(int x,int up,int cur)
{
    rt[x][0]=up;
    high[x]=cur;
    for(int i(1);i<=log[x];++i)
    {
        rt[x][i]=rt[rt[x][i-1]][i-1];
    }
    repg(i,x)
    {
		dep[to[i]]=dep[x]+1;
        init(to[i],x,max(cur,to[i]));
    }
}
inline int lca(int u,int v)
{
	if(dep[u]<dep[v]) u^=v^=u^=v;
	int t=dep[u]-dep[v];
	for(int i(0);t;++i)
	{
		if(t&1) u=rt[u][i];
		t>>=1;
	}
	if(u==v) return u;
	for(int i(log[dep[u]]);i>=0;--i)
	{
		if(rt[u][i]!=rt[v][i])
		{
			u=rt[u][i],v=rt[v][i];
		}
	}
	return rt[u][0];
}
int main()
{
    int n,m,t,q,ans;
    read(n);
    rep(v,1,n)
    {
        read(m);
        add(m,v);
    }
    init_log();
    init(0,0,0);
    read(q);
    while(q--)
    {
        read(m),read(ans);
        rep(i,1,m)
        {
            read(t),ans=lca(t,ans);
        }
        write(high[ans]),putchar('\n');
    }
    return 0;
}

被#21卡WA了过不去求大佬调

2024/10/4 15:00
加载中...