1 条题解

  • 0
    @ 2024-7-27 15:21:06
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    const int N=1e6+10; 
    int n,m;
    int deep[N],st[N][40];
    int head[N],next[N],w[N],to[N];
    int id_star=0;
    inline void add(int x,int y)
    {
        id_star++;
        to[id_star]=y;
        next[id_star]=head[x];
        head[x]=id_star;
    }
    inline int read()
    {
        int x=0,f=1;char ch=getchar();
        while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
        while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
        return x*f;
    }
    inline void write(int x)
    {
        if(x<0)
    	{
            putchar('-');
            x=-x;
        }
        if(x>9) 
            write(x/10);
        putchar(x%10+'0');
    	printf("\n");
    }
    void dfs(int id,int father)
    {
    	deep[id]=deep[father]+1;
    	st[id][0]=father;
    	
    	for(int i=1;(1<<i) <= deep[id]+1;i++)
    		st[id][i]=st[st[id][i-1]][i-1];
    
        for(int j=head[id];j;j=next[j])
        	if(to[j]!=father)
    			dfs(to[j],id);
    }
    inline int find(int u,int v)
    {
    	if(deep[u]>deep[v])swap(u,v);
    	for(int i=log2(deep[v])+1;i>=0;i--)
    	{
    		if(deep[u]<=deep[st[v][i]])
    			v=st[v][i];
    		if(u==v)return v;
    	}
    	for(int i=log2(deep[v])+1;i>=0;i--)
    	{
    		if(st[u][i]!=st[v][i])
    		{
    			u=st[u][i];v=st[v][i];
    		}
    	}
    	return st[u][0];
    }
    int main()
    {
    	n=read();
    	for(int i=1;i<=n-1;i++)
    	{
    		int x,y;
    		x=read();y=read();
    		add(x,y);
    		add(y,x);
    	}
    	deep[0]=0;
    	dfs(1,0);
    	m=read();
    	for(int i=1;i<=m;i++)
    	{
    		int x,y;
    		x=read();y=read();
    		int k=find(x,y);
    		k=deep[k];
    		printf("%d\n",deep[x]+deep[y]-2*k); 
    	}
    }
    
    • 1

    信息

    ID
    457
    时间
    1000ms
    内存
    512MiB
    难度
    10
    标签
    递交数
    4
    已通过
    3
    上传者