ZOJ 1141 简单的题目就用简单的代码

前言

因为我在做题目的过程中，WA了（最后发现是数组开小了的缘故），我以为我方法错误。然后百度一下，满屏的LCA在线/离线算法。加上长篇代码。为了拯救茫茫的ACMer，我决定吐槽一下在这题中使用LCA算法的人

附上 LCA算法的简介

题意

给出一颗树，给出若干个查询，每个查询是树的两个节点，要求的是这两个节点的最近公共祖先。最后总计每个数作为最近公共祖先出现的次数。说白了就是最近公共祖先问题。

解析

的确，LCA是用于求最近公共祖先的一种有效算法，但是由于思想比较复杂（从根节点开始搜索）且代码量太大了（随便找了一篇就是180行的长度），所以在这里并不推荐用。如果只是要A这道题，那大可以这样

比如要查(3,4)最近公共祖先
从3开始往上走，得到：[3,2,5]
从4开始往上走，得到：[4,5]
然后倒序遍历，5和5相同，继续比较2和4，2和4不同，则上一个公共祖先 5 就是最近的公共祖先

再比如要查(2,3)最近公共祖先
从2开始往上走，得到：[2,5]
从3开始往上走，得到[3,2,5]
然后倒序遍历，5和5相同，继续比较2和2也相同，继续比较3和X(X表示越界，比较失败)，则上一个公共祖先2就是最近的公共祖先

LCA算法在于从根节点开始遍历，在深度优先搜索的过程中对结点进行“染色”操作。我觉得至少在这里，貌似简单的“白话文”（如上题解过程）更能让人理解，简单的题目，就用简单的理解+简单的代码，简单也是一种习惯

AC代码

#include <iostream>
#include <stdio.h>
#include <string.h>
#define maxn 101000
using namespace std;
int dp1[maxn],dp2[maxn],dp[maxn],tree[maxn];
int main(int argc, const char * argv[]) {
    int n,m,p,d,len1,len2;
    char ch;
    while(cin>>n){
        memset(dp, 0, sizeof(dp));
        memset(tree, 0, sizeof(tree));
        while(n--){
            scanf("%d:(%d)",&p,&d);
            for(int i=0; i<d; i++){
                scanf("%d",&m);
                tree[m] = p;
            }
        }
        cin>>m;
        for(int j=0; j<m; j++){
            len1 = 0; len2 = 0;
            cin>>ws>>ch>>p>>ch>>d>>ch;
            while(p){
                dp1[len1++] = p;
                p = tree[p];
            }
            while(d){
                dp2[len2++] = d;
                d = tree[d];
            }
            while(dp1[--len1]==dp2[--len2]);
            dp[dp1[len1+1]]++;
        }
        for(int i=1; i<=1010; i++)
            if(dp[i]) cout<<i<<":"<<dp[i]<<endl;
    }
    return 0;
}