倍增求LCA

时间复杂度O(nlogn)

模板

#include 
     
      #include 
      
       #include 
       
        #include
        
         using namespace std;const int maxn = 10007;const int DEG = 20;int head[maxn*2],nxt[maxn*2],to[maxn*2],tot;void init(){    tot=0;    memset(head,0,sizeof(head));    memset(nxt,0,sizeof(nxt));}void add(int u,int v){    ++tot;    to[tot]=v;    nxt[tot]=head[u];    head[u]=tot;}int fa[maxn][DEG];  //fa[i][j]表示结点i的第2^j个祖先int deg[maxn];      //深度数组void bfs(int root){    queue
         
          que;    deg[root]=0;    fa[root][0]=root;    que.push(root);    while(!que.empty())    {        int tmp=que.front();        que.pop();        for(int i=1;i
          
           deg[v]) swap(u,v); int hu=deg[u],hv=deg[v]; int tu=u,tv=v; for(int det=hv-hu,i=0;det;det>>=1,i++) if(det&1) tv=fa[tv][i]; if(tu==tv) return tu; for(int i=DEG-1;i>=0;i--) { if(fa[tu][i]==fa[tv][i]) continue; tu=fa[tu][i]; tv=fa[tv][i]; } return fa[tu][0];}bool flag[maxn];int main(){ int tt,n,u,v; scanf("%d",&tt); while(tt--) { init(); scanf("%d",&n); memset(flag,false,sizeof(flag)); for(int i=1;i
          
         
        
       
      
     

---

POJ1330

分析

模板题

---

 

SPOJ COT

分析

根据dfs序建主席树，lca求最近公共祖先结点后，正常的按照主席树查询第k大即可

---