?id=1330
给一个有根树，，一个查询节点(u,v)的最近公共祖先
836K 16MS
maxn=10005;;vis[maxn];answer[<int> que[maxn];struct Edge{int to;int next;}edge[maxn<<1];int head[maxn],tot;void addedge(int u,int v){edge[tot].to=v;edge[tot].next=head[u];head[u]=tot++;}void Init(){tot=0;memset(in,0,sizeof(in));memset(f,-1,sizeof(f));memset(head,-1,sizeof(head));memset(vis,false,sizeof(vis));memset(ancestor,0,sizeof(ancestor));for(int i=1;i<=n;++i){que[i].clear();}}int find(int x){return f[x]==-1 ?x:f[x]=find(f[x]);}void Union(int u,int v){int t1=find(u);int t2=find(v);if(t1!=t2) f[t2]=t1;}void LCA(int u){ancestor[u]=u;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].to;if(vis[v]) continue;LCA(v);Union(u,v);ancestor[find(v)]=u;//可省略}vis[u]=true;int sz=que[u].size();for(int i=0;i<sz;++i){int v=que[u][i];if(vis[v]){printf(“%d\n”,ancestor[find(v)]);//可替换find(v)}}}int main(){//freopen(“in.txt”,”r”,stdin);int T,u,v,w;cin>>T;while(T–){scanf(“%d”,&n);Init();for(int i=0;i<n-1;++i){scanf(“%d%d”,&u,&v);if(u!=v){addedge(u,v);in[v]++;}}scanf(“%d%d”,&u,&v);que[u].push_back(v);que[v].push_back(u);for(int i=1;i<=n;++i){if(in[i]==0){LCA(i);break;}}}return 0;}
接受失败也等于给了自己从零开始的机会，接受失败更是一种智者的宣言和呐喊;
