题意：一棵n个结点的有根树，求一些结点对的最近公共祖先，输出各个结点作为公共祖先的次数（正数）（n <= 900）。
题目链接：http://poj.org/problem?id=1470
——>>明写着的LCA题目。。。第一次，不大理解离线算法，打了个lca[][]的表，限时2s。。。1313ms飘过。。。想清楚离线思路后，用邻接表把询问的结点对先存起来，不打表。。。438msA掉。。。
离线写法：
#include <cstdio>
#include <cstring>
#include <queue>using namespace std;const int maxn = 900 + 10;
const int maxm = maxn * maxn;int N, root;
int head[maxn], nxt[maxn], v[maxn], ecnt; //邻接表用
int qhead[maxn], qnxt[maxm], qv[maxm];
int pa[maxn], fa[maxn], ret[maxn]; //pa[i]表示原树中结点i的你结点，fa[i]表示并查集中结点i的父结点
bool vis[maxn]; //LCA用void init(){memset(pa, -1, sizeof(pa)); //找根用memset(head, -1, sizeof(head)); //初始化邻接表memset(qhead, -1, sizeof(qhead)); //初始化邻接表ecnt = 0;memset(vis, 0, sizeof(vis)); //LCA用memset(ret, 0, sizeof(ret));
}void addEdge(int uu, int vv){ //邻接表加边v[ecnt] = vv;nxt[ecnt] = head[uu];head[uu] = ecnt;ecnt++;
}void qaddEdge(int uu, int vv){ //邻接表加边qv[ecnt] = vv;qnxt[ecnt] = qhead[uu];qhead[uu] = ecnt;ecnt++;
}int Find(int x){return x == fa[x] ? x : (fa[x] = Find(fa[x]));
}void LCA(int x){ //在x及其子树中，求所有结点的最近公共祖先(LCA)fa[x] = x;for(int e = head[x]; e != -1; e = nxt[e]){LCA(v[e]);fa[v[e]] = x;}vis[x] = 1;for(int e = qhead[x]; e != -1; e = qnxt[e]) if(vis[qv[e]]) ret[Find(qv[e])]++;
}void read(){ //读入int uu, vv, cnt;for(int i = 1; i <= N; i++){scanf("%d:(%d)", &uu, &cnt);for(int j = 0; j < cnt; j++){scanf("%d", &vv);addEdge(uu, vv);pa[vv] = uu;}}
}void solve(){for(root = 1; pa[root] != -1; root++); //找根int M, a, b;scanf("%d", &M);while(M--){while(getchar() != '(');scanf("%d%d", &a, &b);qaddEdge(a, b);qaddEdge(b, a); //此处底部要用双向边while(getchar() != ')');}LCA(root);for(int i = 1; i <= N; i++) if(ret[i]) printf("%d:%d\n", i, ret[i]);
}int main()
{while(scanf("%d", &N) == 1){init();read();solve();}return 0;
}
打表写法：
#include <cstdio>
#include <cstring>
#include <queue>using namespace std;const int maxn = 900 + 10;int N, root;
int head[maxn], nxt[maxn], v[maxn], ecnt; //邻接表用
int pa[maxn], fa[maxn], lca[maxn][maxn], ret[maxn]; //pa[i]表示原树中结点i的你结点，fa[i]表示并查集中结点i的父结点
bool vis[maxn]; //LCA用void init(){memset(pa, -1, sizeof(pa)); //找根用memset(head, -1, sizeof(head)); //初始化邻接表ecnt = 0;memset(vis, 0, sizeof(vis)); //LCA用memset(lca, 0, sizeof(lca));memset(ret, 0, sizeof(ret));
}void addEdge(int uu, int vv){ //邻接表加边v[ecnt] = vv;nxt[ecnt] = head[uu];head[uu] = ecnt;ecnt++;
}int Find(int x){return x == fa[x] ? x : (fa[x] = Find(fa[x]));
}void LCA(int x){ //在x及其子树中，求所有结点的最近公共祖先(LCA)fa[x] = x;for(int e = head[x]; e != -1; e = nxt[e]){LCA(v[e]);fa[v[e]] = x;}vis[x] = 1;for(int i = 1; i <= N; i++)if(vis[i] && !lca[x][i])lca[x][i] = lca[i][x] = Find(i);
}void read(){ //读入int uu, vv, cnt;for(int i = 1; i <= N; i++){scanf("%d:(%d)", &uu, &cnt);for(int j = 0; j < cnt; j++){scanf("%d", &vv);addEdge(uu, vv);pa[vv] = uu;}}
}void solve(){for(root = 1; pa[root] != -1; root++); //找根LCA(root);int M, a, b;scanf("%d", &M);while(M--){while(getchar() != '(');scanf("%d%d", &a, &b);ret[lca[a][b]]++;while(getchar() != ')');}for(int i = 1; i <= N; i++) if(ret[i]) printf("%d:%d\n", i, ret[i]);
}int main()
{while(scanf("%d", &N) == 1){init();read();solve();}return 0;
}