题目链接
题意
给定一棵树和树上的两个结点,输出这两个结点的最近公共祖先。
思路
题目给定了两个结点a,b,我的思路是分别求出a,b的所有祖先,保存在va,vb中,然后遍历va和vb,由于va和vb中的结点是按离树根越来越近排列的,所以va和vb中第一个重合的元素即为a,b的最近公共祖先。在树的表示方面,使用数组来存储树。
代码
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 const int N = 10000 + 10; 8 int p[N]; //p[i]表示结点i的双亲结点 9 vector va; //结点a的所有祖先结点10 vector vb; //结点b的所有祖先结点11 12 void find_ancestor(int c, vector & v) //找到c的祖先,存储在v中13 {14 if(p[c] == 0) //树的根结点15 {16 v.push_back(c);17 return;18 }19 20 v.push_back(c);21 find_ancestor(p[c], v);22 }23 24 void get_nca(int a, int b)25 {26 va.clear();27 vb.clear();28 find_ancestor(a, va);29 find_ancestor(b, vb);30 31 int la = va.size();32 int lb = vb.size();33 34 for(int i=0; i >t;52 while(t--)53 {54 memset(p, 0, sizeof(p));55 int n;56 cin>>n;57 for(int i=0; i >a>>b;61 p[b] = a;62 }63 int a, b;64 cin>>a>>b;65 get_nca(a, b);66 }67 return 0;68 }