题意: 给出一颗有 n 个节点的树，问u 和 v 的最近公共祖先。
分析： rmq ：对树先进行深搜，记录深搜序列和每个序列的深度，将最近公共祖先的询问转化为区间最值问题。
tarjan：保存所有询问，在深搜的时候同时保存答案。
rmq_在线算法 #include#include #include #define clr(x)memset(x,0,sizeof(x))#define maxn 10005struct node{ int to,next;}e[100000];int tot;int head[maxn];void add(int s,int u){ e[tot].to=u; e[tot].next=head[s]; head[s]=tot++;}int dp[maxn<<1][16]; // d[] 数组的区间最值int x[maxn<<1]; // dfs 后的节点序列int d[maxn<<1]; // e[] 中相应节点的深度int r[maxn]; // 节点 i 在 e[] 中第一次出现的位置int v[maxn]; int f[maxn];int min(int i,int j){ return d[i]
tarjan_离线算法 #include#include #define maxn 10005#define clr(x)memset(x,0,sizeof(x))int f[maxn];struct node{ int to,next,lca;}e[maxn],qe[maxn];int t1,t2;int head[maxn],qhead[maxn];void add1(int s,int u){ e[t1].to=u; e[t1].next=head[s]; head[s]=t1++;}void add2(int s,int u){ qe[t2].to=u; qe[t2].next=qhead[s]; qhead[s]=t2++; qe[t2].to=s; qe[t2].next=qhead[u]; qhead[u]=t2++;}int find(int x){ return f[x]==x?f[x]:(f[x]=find(f[x])); }int v[maxn];void LCA(int u){ f[u]=u; int i,k; v[u]=1; for(i=head[u];i!=-1;i=e[i].next) { k=e[i].to; if(!v[k]) { LCA(k); f[k]=u; } } for(i=qhead[u];i!=-1;i=qe[i].next) { k=qe[i].to; if(v[k]) { qe[i].lca=find(k); qe[i^1].lca=qe[i].lca; } }}int degree[maxn];void init(){ t1=t2=0; memset(qhead,-1,sizeof(qhead)); memset(head,-1,sizeof(head)); clr(degree); clr(v);}int main(){ int t,n,m,a,b,i; scanf("%d",&t); while(t--) { scanf("%d",&n); init(); for(i=1;i