其实这是一个裸求LCA的题目，我使用的是离线的Tarjan算法，但是这个题的AC对于我来说却很坎坷……首先是RE，我立马想到数组开小了，然后扩大了数组，MLE了……接着把数组调整适当大小，又交了一发，嗯？居然WA了，一定是我姿势不对，我换个编译器交一下，结果还是WA……这就比较尴尬了，最后审题目，发现了，我以为第一个输入的点就是根节点，其实不是，我们还需要找到入度为0的点来处理，这里做一个标记就可以了。还有就是题目的输入稍微有点坑，尤其是第二次输入，题目中说忽略所有空白，这就需要比较好的处理方法了，我采用的是while的方法，当然方法肯定是有很多的。代码如下：
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
#define N 1010
int head[N],qhead[N],n,tot,qtot;
struct Edge{
int to,nxt;
}edge[N*N];
void addedge(int a,int b){
edge[tot].to = b;
edge[tot].nxt = head[a];
head[a] = tot++;
}
Edge query[N*N];
void addquery(int a,int b){
query[qtot].to = b;
query[qtot].nxt = qhead[a];
qhead[a] = qtot++;
}
int vis[N],fa[N],ans[N];
int Find(int x){
return x == fa[x] ? fa[x] : fa[x] = Find(fa[x]);
}
void tarjan(int u){
vis[u] = ;
fa[u] = u;
int v,LCA;
for(int i = qhead[u];i != -;i = query[i].nxt){
v = query[i].to;
if(vis[v]){
LCA = Find(v);
//printf("%d->%d LCA = %d\n",u,v,LCA);
ans[LCA]++;
}
}
for(int i = head[u];i != -;i = edge[i].nxt){
v = edge[i].to;
if(!vis[v]){
tarjan(v);
fa[v] = u;
}
}
return ;
}
int main(){
int a,b,m,num,anc,mark[N];
while(~scanf("%d",&n)){
tot = ;
memset(head,-,sizeof(head));
memset(mark,,sizeof(mark));
for(int i = ;i <= n;i++){
scanf("%d:(%d) ",&a,&num);
for(int j = ;j < num;j++){
scanf("%d",&b);
mark[b] = ;
addedge(a,b);
}
// for(int j = head[a];j != -1;j = edge[j].nxt){
// printf("%d->%d\n",a,edge[j].to);
// }
fa[i] = i;
}
for(int i = ;i <= n;i++){
if(!mark[i]){
anc = i;
break;
}
}
memset(qhead,-,sizeof(qhead));
qtot = ;
scanf("%d",&m);
// getchar();
char ch; int cnt = ;
while(~scanf("%c",&ch)){
if(ch == '('){
scanf("%d %d)",&a,&b);
addquery(a,b);
addquery(b,a);
cnt++;
}
if(cnt==m) break;
}
memset(vis,,sizeof(vis));
memset(ans,,sizeof(ans));
tarjan(anc);
for(int i = ;i <= n;i++){
if(ans[i]) printf("%d:%d\n",i,ans[i]);
}
}
return ;
}