首页 > 代码库 > 【LCA】0.1单组不会倍增的暴力的树上最近公共祖先
【LCA】0.1单组不会倍增的暴力的树上最近公共祖先
0.1就是0.1……弱的不行……只是暂时存一下为以后高大上的正解作铺垫
Q:LCA都不会你学什么OI？
A:我学不了OI了我要滚粗……
适当解释：
第一行输入点数n以及两个要查询的点q1,q2
第二行输入每个点父亲father[i]
一行输出ans==最近公共祖先……
不会倍增……写了个看起来是正解其实是暴力的东东……
#include<iostream>#include<cstdlib>#include<cstdio>using namespace std;int father[500];int q1,q2,h1,h2,n,t1,t2,ans,s1,s2,jump;bool flag;bool pd(int q1,int q2){ if (father[q1]==q2) {ans=q2;flag=false;return false;} if (father[q2]==q1) {ans=q1;flag=false;return false;} if (q1==q2) {ans=q1;flag=false;return false;} return true;}int main(){ cin>>n>>q1>>q2; for (int i=1;i<=n;i++) cin>>father[i]; t1=q1;t2=q2; while (t1!=0) {t1=father[t1];h1++;} while (t2!=0) {t2=father[t2];h2++;} int gap=abs(h1-h2); if (h1<h2) { while (gap>0) { q2=father[q2]; gap--; } } else { while (gap>0) { q1=father[q1]; gap--; } } pd(q1,q2); flag=true; while (q1!=q2) { s1=q1;s2=q2;jump=233; while ((q1!=0)&&(q2!=0)&&(jump>0) ) { q1=father[q1]; q2=father[q2]; jump--; } } q1=s1;q2=s2; while ( (q1!=0) && (q2!=0) && (pd(q1,q2)) && flag) { if (flag==false) break; q1=father[q1]; q2=father[q2]; } cout<<"ans=="<<ans<<endl; return 0; }
我一直觉得 && (pd(q1,q2)) 写得真TM好…………我这么弱居然写出了这么强大的东西…………（hzwer：那你要flag干嘛？我：囧）
【LCA】0.1单组不会倍增的暴力的树上最近公共祖先
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。