pku 1330 Nearest Common Ancestors
题目链接：
题目大意：
给定一棵树的边关系，注意是有向边，因为这个WA一发。然后N个顶点给出了N-1有向边，求一对点之间的最近公共祖先
思路：
裸的离线tarjan Lca即可，但注意是有向边，需要先找出根节点，数组标记。其次要注意前向星存的时候只存一条边即可
代码：
#include <iostream>
#include <string.h>
using namespace std;
const int maxn = 10005;
struct node {
int to,next;
} edges[maxn*2];
int n,head[maxn],f[maxn],vis[maxn],cnt,u,v,res,fir[maxn];
inline void addedge(int u, int v) {
edges[cnt].to=v;
edges[cnt].next=head[u];
head[u]=cnt++;
}
inline void init() {
memset(vis,0,sizeof(vis));
memset(head,-1,sizeof(head));
memset(fir,1,sizeof(fir));
for(int i=1; i<=n; ++i) f[i]=i;
cnt=0;
}
inline int Find(int x) {
return x == f[x] ? x : f[x] = Find(f[x]);
}
inline void tarjan(int s) {
vis[s]=1;
int t;
for(int i=head[s]; i!=-1; i=edges[i].next) {
t=edges[i].to;
if(!vis[t]) {
tarjan(t);
f[t]=s;
}
}
if(s==u&&vis[v]) res=Find(v);
else if(s==v&&vis[u]) res=Find(u);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t,root;
cin>>t;
while(t--) {
cin>>n;
init();
for(int i=1; i<n; ++i) {
cin>>u>>v;
fir[v]=0;
addedge(u,v);
}
cin>>u>>v;
for(int i=1; i<=n; ++i) {
if(fir[i]) {
root=i;
break;
}
}
tarjan(root);
cout<<res<<endl;
}
return 0;
}