题目地址：POJ 1470 LCA模板题。。输入有点坑，，还有输入的第一个结点不一定是根节点。 代码如下：
using namespace std;#define LL __int64#define pi acos(-1.0)const int mod=1e9+7;const int INF=0x3f3f3f3f;const double eqs=1e-9;const int MAXN=1000+10;int F[MAXN<<1], fir[MAXN], rmq[MAXN<<1], ans[MAXN], deg[MAXN];int head[MAXN], cnt, tot;struct node {int u, v, next;} edge[MAXN<<1];void add(int u, int v){edge[cnt].v=v;edge[cnt].next=head[u];head[u]=cnt++;}void dfs(int u, int fa, int dep){F[++tot]=u;fir[u]=tot;rmq[tot]=dep;for(int i=head[u]; i!=-1; i=edge[i].next) {int v=edge[i].v;if(v==fa) continue ;dfs(v,u,dep+1);F[++tot]=u;rmq[tot]=dep;}}struct ST {int dp[MAXN<<1][20], i, j;void init() {for(i=1; i<=tot; i++) {dp[i][0]=i;}for(j=1; (1<<j)<=tot; j++) {for(i=1; i<=tot-(1<<j-1)+1; i++) {dp[i][j]=rmq[dp[i][j-1]]<rmq[dp[i+(1<<j-1)][j-1]]?dp[i][j-1]:dp[i+(1<<j-1)][j-1];}}}int Query(int l, int r) {if(r<l) swap(l,r);int k=0;while((1<<k+1)<=r-l+1) k++;return rmq[dp[l][k]]<rmq[dp[r+1-(1<<k)][k]]?dp[l][k]:dp[r+1-(1<<k)][k];}} st;void init(){memset(head,-1,sizeof(head));memset(ans,0,sizeof(ans));memset(deg,0,sizeof(deg));cnt=tot=0;}int main(){int n, m, i, j, u, v, tmp;while(scanf(“%d”,&n)!=EOF) {init();for(i=0; i<n; i++) {scanf(“%d”,&u);scanf(“:(%d)”,&m);while(m–) {scanf(“%d”,&v);add(u,v);add(v,u);deg[v]++;}}for(i=1; i<=n; i++) {if(!deg[i]) {dfs(i,-1,0);break;}}st.init();scanf(“%d”,&m);while(m–) {char c=getchar();while(c!='(‘) {c=getchar();}scanf(“%d %d)”,&u,&v);ans[F[st.Query(fir[u],fir[v])]]++;}for(i=1; i<=n; i++) {if(ans[i]) {printf(“%d:%d\n”,i,ans[i]);}}}return 0;}
擒龙要下海，打虎要上山。
