题意
给定一个有根树，查询若干组（u，v）的lca，输出每个结点作为lca的次数。如果一次也没有，则不输出。
解题
根据根结点没有其他结点指向这一特性确定根，然后调用tarjan算法离线处理所有查询的lca。最后统计并输出即可。
AC代码
//610ms 7.2MB
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int maxn=1e3+100;
const int maxm=3e5+100;//查询数可能较大
struct edge
{int from,to,next,lca;
}e[maxn<<1],q[maxm<<1];
int par[maxn],n;
int ans[maxn];
int head[maxn],cnt,first[maxn],tot,vis[maxn];
void add_edge(int u,int v)//树图连边
{e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;
}
void _add(int u,int v)//查询连边，都是单向边
{q[++tot].to=v;q[tot].from=u;q[tot].next=first[u];first[u]=tot;
}
void init()//边以及并查集的初始化
{memset(ans,0,sizeof(ans));memset(head,-1,sizeof(head));memset(first,-1,sizeof(first));memset(vis,0,sizeof(vis));for(int i=0;i<=n;i++) par[i]=i;tot=-1;//查询边的编号从0开始cnt=-1;//树图边的编号从0开始
}
int find(int x)//查询祖先结点
{return par[x]==x?x:par[x]=find(par[x]);
}void unit(int x,int y)//合并
{int fx=find(x),fy=find(y);if(fx==fy) return ;par[fx]=fy;
}
void tarjan(int u)//dfs+并查集
{vis[u]=1;for(int i=head[u];i!=-1;i=e[i].next){int v=e[i].to;if(vis[v]) continue;tarjan(v);unit(v,u);}for(int i=first[u];i!=-1;i=q[i].next){int v=q[i].to;if(!vis[v]) continue;q[i].lca=q[i^1].lca=find(v);}
}
int is_child[maxn];
int main()
{int m;while(~scanf("%d",&n)){init();int root;//根结点是没有结点指向的结点memset(is_child,0,sizeof(is_child));for(int i=1; i<=n; i++){int u;scanf("%d",&u);scanf(":(%d)",&m);while(m--){int v;scanf("%d",&v);is_child[v]=1;add_edge(u,v);add_edge(v,u);}}int Q;scanf("%d",&Q);for(int i=1; i<=Q; i++){while(1){if(getchar()=='(')break;}int u,v;scanf("%d%d)",&u,&v);_add(u,v);_add(v,u);}for(int i=1;i<=n;i++)if(!is_child[i]) root=i;tarjan(root);for(int i=0; i<Q; i++){int id=i*2,lca=q[id].lca;ans[lca]++;}for(int i=1; i<=n; i++)if(ans[i])printf("%d:%d\n",i,ans[i]);}return 0;
}