基本题,留着模板
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <climits>//形如INT_MAX一类的
using namespace std;
vector<int>lz[10005],que[10005];
int vis[10005],nopa[10005];
int n,m,pa[10005],s,e;
int find(int x)
{
if(pa[x] != x)
return pa[x] = find(pa[x]);
else
return x;
}
void LCA(int u)
{
int i,j;
for(i=0; i<lz[u].size(); i++) //递归处理
{
LCA(lz[u][i]);
pa[lz[u][i]] = u;
}
vis[u] = 1;
for(i=0; i<que[u].size(); i++) //询问处理
{
if(vis[que[u][i]])
{
cout << find(que[u][i]) << endl;
return;
}
}
}
int main()
{
int t,i,j,a,b;
cin >> t;
while(t--)
{
cin >> n;
for(i=1; i<=n; i++) //初始化
{
lz[i].clear();
que[i].clear();
vis[i] = 0;
nopa[i] = 0;
pa[i] = i;
}
for(i=1; i<n; i++)
{
scanf("%d%d",&a,&b);
lz[a].push_back(b); //算是单向边,a是b的父结点
nopa[b] = 1;
}
scanf("%d%d",&s,&e);
que[s].push_back(e);
que[e].push_back(s); //询问两点连起关系
for(i=1; i<=n; i++)
{
if(!nopa[i]) //从总结点开始LCA
{
LCA(i);
}
}
}
return 0;
}
分享到:
相关推荐
2. bool nodePath (bstNode* pRoot, int value, std::vector*>& path) 3. { 6
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj 2763 程序 线段树 LCA 2000MS AC
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj分类poj分类poj分类poj分类
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
北大POJ2002-Squares 解题报告+AC代码
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
poj 1001答案
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
POJ2968代码有用,欢迎下载,POJ代码