计蒜客祖宗十九代

╰+哭是因爲堅強的太久メ 2022-05-14 01:26 166阅读 0赞

[题目传送门][Link 1]  
简单LCA  
代码：

#include<bits/stdc++.h>
    using namespace std;
    
    const int maxn=10000+100;
    
    int dp[maxn][20],fa[maxn],du[maxn],in[maxn];
    
    struct Edge{
    	
    	int to,next;
    }edge[maxn];
    int head[maxn],tot;
    int n;
    
    void DFS(int u,int d,int f){
    	
    	fa[u]=dp[u][0]=f;
    	du[u]=d;
    	for(int i=1;(1<<i)<=d;i++) dp[u][i]=dp[dp[u][i-1]][i-1];
    	for(int i=head[u];i!=-1;i=edge[i].next){
    		
    		Edge e=edge[i];
    		int v=e.to;
    		if(v==f) continue;
    		DFS(v,d+1,u);
    	}
    }
    
    int main(){
    	
    	int T;
    	scanf("%d",&T);
    	while(T--){
    		
    		scanf("%d",&n);
    		tot=0;
    		for(int i=1;i<=n;i++) head[i]=-1,in[i]=0;
    		for(int i=1;i<n;i++){
    			
    			int u,v;
    			scanf("%d%d",&u,&v);
    			in[v]++;
    			edge[tot].to=v;
    			edge[tot].next=head[u];
    			head[u]=tot++;
    		}
    		memset(dp,0,sizeof(dp));
    		int node=0;
    		for(int i=1;i<=n && !node;i++) if(!in[i]) node=i;
    		DFS(node,0,-1);
    		int x,y;
    		scanf("%d%d",&x,&y);
    		if(du[x]<du[y]) swap(x,y);
    		int ci=du[x]-du[y];
    		for(int i=0;;i++){
    			
    			if((1<<i)>ci) break;
    			if((ci>>i)&1) x=dp[x][i];
    		}
    		if(x==y){
    			
    			printf("%d\n",x);
    			continue;
    		}
    		for(int i=15;i>=0;i--){
    			
    			if(dp[x][i]!=dp[y][i]) x=dp[x][i],y=dp[y][i];
    		}
    		printf("%d\n",dp[x][0]);
    	}
    }

[Link 1]: https://nanti.jisuanke.com/t/24803

发表评论取消回复

表情：

评论列表（有 0 条评论，166人围观）

还没有评论，来说两句吧...

相关阅读

相关计蒜客跳跃游戏（dfs）

给定一个非负整数数组，假定你的初始位置为数组第一个下标。数组中的每个元素代表你在那个位置能够跳跃的最大长度。请确认你是否能够跳跃到数组的最后一个下标。例如：A=\[

女爷i/ 2024年02月17日 22:03/ 0 赞/ 56 阅读

相关计蒜客三值排序（贪心）

排序是一种很频繁的计算任务。一个实际的例子是，当我们给某项竞赛的优胜者按金银铜牌排序的时候。在这个任务中可能的值只有三种1，2和3。我们用交换的方法把他排成升序的。写一个程

悠悠/ 2024年02月17日 22:03/ 0 赞/ 47 阅读

相关计蒜客 T1200 Minecraft

题目链接：[https://nanti.jisuanke.com/t/T1200][https_nanti.jisuanke.com_t_T1200] 解题思路：因为立方体的

ゝ一世哀愁。/ 2023年07月09日 05:24/ 0 赞/ 36 阅读

相关 2017计蒜客第二场（AB）

A ：百度年会盛况空前，每个部门的年会活动也是非常有趣。某部门的年会中进行了一个有趣的游戏：一张方桌上有四边，每边可以坐一人，每人面前摆放一排长方形木块。我们一次

迷南。/ 2022年06月15日 02:44/ 0 赞/ 170 阅读

相关计蒜客---三值排序

排序是一种很频繁的计算任务。一个实际的例子是，当我们给某项竞赛的优胜者按金银铜牌排序的时候。在这个任务中可能的值只有三种1，2和3。我们用交换的方法把他排成升序的。写一个程

墨蓝/ 2022年06月14日 10:23/ 0 赞/ 207 阅读

相关计蒜客祖宗十九代

[题目传送门][Link 1] 简单LCA 代码： include<bits/stdc++.h> using namespace std;

╰+哭是因爲堅強的太久メ/ 2022年05月14日 01:26/ 0 赞/ 167 阅读

相关计蒜客奇异家庭

[题目传送门][Link 1] dp\[i\]\[j\] – i 个节点不超过 j 层的方案数有dp\[i\]\[j\]+=dp\[t\]\[j-1\]\dp\[i-t

末蓝、/ 2022年05月14日 00:26/ 0 赞/ 225 阅读

相关计蒜客踏青 dfs

题目： https://www.jisuanke.com/course/2291/182234 思路：紫书P163联通块问题。 1.遍历所有块，找到草地，判断合法性，

系统管理员/ 2022年01月06日 11:47/ 0 赞/ 268 阅读

相关【计蒜客】走迷宫

总而言之，关于迷宫好像大部分都是搜索题.... 先看一下题：（数据范围好小啊给一个n行m列的2维的迷宫，`'S'`表示迷宫的起点，`'T'`表示迷宫的

╰+哭是因爲堅強的太久メ/ 2021年12月21日 20:55/ 0 赞/ 314 阅读

相关计蒜客 - 汉诺塔

问题: ![1516087-20190501155629805-481143157.png][] 思路: 汉诺塔问题非常经典，不懂推荐去看B站正月点灯笼老师的对于汉诺塔的

悠悠/ 2021年12月03日 15:55/ 0 赞/ 333 阅读