【基础练习】【倍增LCA】codevs1503 愚蠢的宠物

今天药忘吃喽~ 2022-08-09 00:50 152阅读 0赞

题目描述 Description

大家都知道，sheep有两只可爱的宠物（一只叫神牛，一只叫神菜）。有一天，sheep带着两只宠物到狗狗家时，这两只可爱的宠物竟然迷路了……

狗狗的家因为常常遭到猫猫的攻击，所以不得不把家里前院的路修得非常复杂。狗狗家前院有N个连通的分叉结点，且只有N-1条路连接这N个节点，节点的编号是1-N（1为根节点）。sheep的宠物非常笨，他们只会向前走，不会退后（只向双亲节点走），sheep想知道他们最早什么时候会相遇（即步数最少）。

![1364548659.060.0394817004357.jpg][]

输入描述 Input Description

第1行：一个正整数N，表示节点个数。

第2~N行：两个非负整数A和B，表示A是B的双亲。（保证A,B<=n）

第N+1行：两个非负整数A和B，表示两只宠物所在节点的位置。（保证A,B<=n）

输出描述 Output Description

输出他们最早相遇的节点号。

样例输入 Sample Input

10  
1 2  
1 3  
1 4  
2 5  
2 6  
3 7  
4 8  
4 9  
4 10  
3 6

样例输出 Sample Output

数据范围及提示 Data Size & Hint

对于10%的数据，n<10^6

对于100%的数据，n<=10^6

把前一个题（商务旅行）改了一下，明明有很明显的错误，竟然AC了 足以见得数据有多悲剧···

读入的时候我是默认了父节点之前已经读入过···没想到数据愚蠢的真的都读入过···

算了直接上代码 裸LCA

//codevs1503 ÓÞ´ÀµÄ³èÎï LCA
    //copyright by ametake
    #include
       
        
    #include
        
         
    #include
         
          
    #include
          
           
    using namespace std;
    
    const int maxn=1000000+10;
    int depth[maxn],fa[maxn];
    int head[maxn],to[maxn*2],next[maxn*2];//twice again!!!
    int n,m;
    int et;
    int up[maxn][20];
    
    void dfs(int now)
    {
    	int t=head[now];
    	while (t)
    	{
    		if (depth[to[t]])
    		{
    			t=next[t];
    			continue;
    		}
    		depth[to[t]]=depth[now]+1;//²»ÄÜÐ´depth[now]++ ÕâÑùdepth[now]Ò²»á+1 
    		fa[to[t]]=now;
    		dfs(to[t]);
    		t=next[t];
    	}
    	return;
    }
    
    void doit()
    {
    	for (int i=1;i<=n;i++) up[i][0]=fa[i];
    	for (int j=1;j<=14;j++)
    	{
    		for (int i=1;i<=n;i++)
    		{
    			up[i][j]=up[up[i][j-1]][j-1];
    		}
    	}
    }
    
    int lca(int x,int y)
    {
    	if (depth[x]
           
            =0;i--) { if (up[x][i]!=up[y][i]) { x=up[x][i]; y=up[y][i]; } } return up[x][0]; } int main() { scanf("%d",&n); int x,y; memset(depth,0,sizeof(depth)); depth[1]=1; for (int i=1;i

`——读书破万卷，下笔如有神`

[1364548659.060.0394817004357.jpg]: http://codevs.cn/media/image/1364548659.060.0394817004357.jpg