读入挂

inline void read(int &v){        v = 0;        char c = 0;        int p = 1;        while (c < '0' || c > '9')        {                if (c == '-')                {                        p = -1;                }                c = getchar();        }        while (c >= '0' && c <= '9')        {                v = (v << 3) + (v << 1) + c - '0';                c = getchar();        }        v *= p;}

基本模板

离线:

1 /*Huyyt*/  2 #include
      
         3 #define mem(a,b) memset(a,b,sizeof(a))  4 #define pb push_back  5 using namespace std;  6 typedef long long ll;  7 typedef unsigned long long ull;  8 using namespace std;  9 const int MAXN = 1e5 + 5, MAXM = 1e5 + 5; 10 const int MAXQ = 1e5 + 5; 11 int to[MAXM << 1], nxt[MAXM << 1], Head[MAXN], ed = 1; 12 int value[MAXM << 1]; 13 inline void addedge(int u, int v, int val) 14 { 15         to[++ed] = v; 16         nxt[ed] = Head[u]; 17         value[ed] = val; 18         Head[u] = ed; 19 } 20 int fa[MAXN], d[MAXN], vis[MAXN], LCA[MAXQ], ans[MAXQ]; 21 vector
       
         query[MAXQ], query_id[MAXQ]; 22 void add_query(int x, int y, int id) 23 { 24         query[x].push_back(y), query_id[x].push_back(id); 25         query[y].push_back(x), query_id[y].push_back(id); 26 } 27 int get(int x) 28 { 29         if (x == fa[x]) 30         { 31                 return x; 32         } 33         return fa[x] = get(fa[x]); 34 } 35 void tarjan(int x) 36 { 37         vis[x] = 1; 38         for (int v, i = Head[x]; i; i = nxt[i]) 39         { 40                 v = to[i]; 41                 if (vis[v]) 42                 { 43                         continue; 44                 } 45                 d[v] = d[x] + value[i]; 46                 tarjan(v); 47                 fa[v] = x; 48         } 49         for (int i = 0; i < query[x].size(); i++) 50         { 51                 int v = query[x][i], id = query_id[x][i]; 52                 if (vis[v] == 2) 53                 { 54                         LCA[id] = get(v); 55                         ans[id] = min(ans[id], d[x] + d[v] - 2 * d[LCA[id]]); 56                 } 57         } 58         vis[x] = 2; 59 } 60 int n, m; 61 int u, v, z; 62 int main() 63 { 64         int T; 65         scanf("%d", &T); 66         while (T--) 67         { 68                 scanf("%d %d", &n, &m); 69                 for (int i = 1; i <= n; i++) 70                 { 71                         vis[i] = Head[i] = 0, fa[i] = i; 72                         query[i].clear(), query_id[i].clear(); 73                 } 74                 ed = 0; 75                 for (int i = 1; i < n; i++) 76                 { 77                         scanf("%d %d %d", &u, &v, &z); 78                         addedge(u, v, z), addedge(v, u, z); 79                 } 80                 for (int i = 1; i <= m; i++) 81                 { 82                         scanf("%d %d", &u, &v); 83                         if (u == v) 84                         { 85                                 ans[i] = 0; 86                                 LCA[i] = u; 87                         } 88                         else 89                         { 90                                 add_query(u, v, i); 91                                 ans[i] = 1 << 30; 92                         } 93                 } 94                 tarjan(1); 95                 for (int i = 1; i <= m; i++) 96                 { 97                         printf("%d\n", ans[i]); 98                 } 99         }100         return 0;101 }
       
      

倍增:

for (int j=1;j<=20;j++){        for (int i=1;i<=n;i++) f[i][j]=f[f[i][j-1]][j-1],        minn[i][j]=min(minn[i][j-1],minn[f[i][j-1]][j-1]);    }int lca(int x,int y){    if (dep[x]
     
      =0;i--){        if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];    }    return f[x][0];}int dist(int x,int y){    if (dep[x]
     

 HDU 2586  单树带权LCA

在线:

①倍增

/* Huyyt */#include 
      
       using namespace std;const int maxn = 40001;  //点的最大值const int maxl = 25; //深度的最大值typedef struct{        int from, to, w;} edge; //这个结构体用来存储边vector
       
         edges;vector
        
          G[maxn];//保存边的数组int grand[maxn][maxl];  //x向上跳2^i次方的节点，x到他上面祖先2^i次方的距离int gw[maxn][maxl];   //维护距离的数组int depth[maxn];//深度int root;int n, m;int N; //N的意思是最多能跳几层void addedge(int x, int y, int w)  //把边保存起来的函数{        edge a = {x, y, w}, b = {y, x, w};        edges.push_back(a);        edges.push_back(b);        G[x].push_back(edges.size() - 2);        G[y].push_back(edges.size() - 1);}void dfs(int x)//dfs建图{        for (int i = 1; i <= N; i++) //第一个几点就全部都是0,第二个节点就有变化了,不理解的话建议复制代码输出下这些数组        {                grand[x][i] = grand[grand[x][i - 1]][i - 1];  //倍增 2^i=2^(i-1)+2^(i-1)                gw[x][i] = gw[x][i - 1] + gw[grand[x][i - 1]][i - 1]; //维护一个距离数组                // if(grand[x][i]==0) break;        }        for (int i = 0; i < G[x].size(); i++)        {                edge  e = edges[G[x][i]];                if (e.to != grand[x][0]) //这里我们保存的是双向边所以与他相连的边不是他父亲就是他儿子父亲的话就不能执行，不然就死循环了。                {                        depth[e.to] = depth[x] + 1; //他儿子的深度等于他爸爸的加1                        grand[e.to][0] = x; //与x相连那个节点的父亲等于x                        gw[e.to][0] = e.w; //与x相连那个节点的距离等于这条边的距离                        dfs(e.to);//深搜往下面建                }        }}void Init(){        //n为节点个数        N = floor(log(n + 0.0) / log(2.0));//最多能跳的2^i祖先        depth[root] = 0; //根结点的祖先不存在，用-1表示        memset(grand, 0, sizeof(grand));        memset(gw, 0, sizeof(gw));        dfs(root);//以1为根节点建树}int lca(int a, int b){        if (depth[a] > depth[b])        {                swap(a, b);        //保证a在b上面，便于计算        }        int ans = 0;        for (int i = N; i >= 0; i--) //类似于二进制拆分，从大到小尝试        {                if (depth[a] < depth[b] && depth[grand[b][i]] >= depth[a]) //a在b下面且b向上跳后不会到a上面                {                        ans += gw[b][i], b = grand[b][i];        //先把深度较大的b往上跳                }        }        if (a == b)        {                return ans;        }        for (int j = N; j >= 0; j--) //在同一高度了,他们一起向上跳,跳他们不相同节点，当全都跳完之后grand【a】【0】就是lca,上面有解释哈。        {                if (grand[a][j] != grand[b][j])                {                        ans += gw[a][j];                        ans += gw[b][j];                        a = grand[a][j];                        b = grand[b][j];                }        }        if (a != b) //a等于b的情况就是上面土色字体的那种情况        {                ans += gw[a][0], ans += gw[b][0];        }        return ans;}int main(){        depth[0] = -1;        int t ;        scanf("%d", &t);        while (t--)        {                root = 1;                scanf("%d%d", &n, &m);                for (int i = 1; i < n; i++)                {                        int x, y, w;                        scanf("%d%d%d", &x, &y, &w);                        addedge(x, y, w);                }                Init();                for (int i = 1; i <= m; i++)                {                        int x, y;                        scanf("%d%d", &x, &y);                        printf("%d\n", lca(x, y));                }        }}
        
       
      

离线:

②Tarjan

/*Huyyt*/#include
      
       using namespace std;const int MAXN = 40010;//点的最大值const int MAXQ = 40010;//查询数的最大值inline int readint(){        char c = getchar();        int ans = 0;        while (c < '0' || c > '9')        {                c = getchar();        }        while (c >= '0' && c <= '9')        {                ans = ans * 10 + c - '0', c = getchar();        }        return ans;}//并查集部分int F[MAXN];//需要初始化为-1int find(int x){        if (F[x] == -1)        {                return x;        }        return F[x] = find(F[x]);}void bing(int u, int v){        int t1 = find(u);        int t2 = find(v);        if (t1 != t2)        {                F[t1] = t2;        }}bool vis[MAXN];//访问标记int ancestor[MAXN];//祖先int distence[MAXN];struct Edge{        int to, next, dis;} edge[MAXN * 2];int head[MAXN], tot;void addedge(int u, int v, int d){        edge[tot].to = v;        edge[tot].dis = d;        edge[tot].next = head[u];        head[u] = tot++;}struct Query{        int q, next;        int index;//查询编号} query[MAXQ * 2];int answer[MAXQ];//存储最后的查询结果，下标0~Q-1int h[MAXQ];int tt;int Q;void add_query(int u, int v, int index){        query[tt].q = v;        query[tt].next = h[u];        query[tt].index = index;        h[u] = tt++;        query[tt].q = u;        query[tt].next = h[v];        query[tt].index = index;        h[v] = tt++;}void init(){        tot = 0;        memset(head, -1, sizeof(head));        memset(distence, 0, sizeof(distence));        tt = 0;        memset(h, -1, sizeof(h));        memset(vis, false, sizeof(vis));        memset(F, -1, sizeof(F));        memset(ancestor, 0, sizeof(ancestor));}void getdistence(int x, int pre){        for (int i = head[x]; i != -1; i = edge[i].next)        {                int v = edge[i].to;                if (v == pre)                {                        continue;                }                distence[v] = distence[x] + edge[i].dis;                getdistence(v, x);        }}void LCA(int u){        ancestor[u] = u;        vis[u] = true;        for (int i = head[u]; i != -1; i = edge[i].next)        {                int v = edge[i].to;                if (vis[v])                {                        continue;                }                LCA(v);                bing(u, v);                ancestor[find(u)] = u;        }        for (int i = h[u]; i != -1; i = query[i].next)        {                int v = query[i].q;                if (vis[v])                {                        answer[query[i].index] = distence[v] + distence[u] - 2 * distence[ancestor[find(v)]];                }        }}bool flag[MAXN];int main(){        int T;        T = readint();        int n;        int u, v, k;        int len;        while (T--)        {                n = readint();                Q = readint();                init();                memset(flag, false, sizeof(flag));                for (int i = 1; i < n; i++)                {                        u = readint();                        v = readint();                        len = readint();                        flag[v] = true;                        addedge(u, v, len);                        addedge(v, u, len);                }                for (int i = 0; i < Q; i++)                {                        u = readint();                        v = readint();                        add_query(u, v, i);                }                int root;                for (int i = 1; i <= n; i++)                        if (!flag[i])                        {                                root = i;                                break;                        }                distence[root] = 0;                getdistence(root, -1);                LCA(root);                for (int i = 0; i < Q; i++)                {                        cout << answer[i] << endl;                }        }        return 0;}
      

hihocoder 1062   多树不带权LCA

离线:

①Tarjan

#include
      
       using namespace std;const int MAXN = 410;const int MAXQ = 110;//查询数的最大值inline int readint(){        char c = getchar();        int ans = 0;        while (c < '0' || c > '9')        {                c = getchar();        }        while (c >= '0' && c <= '9')        {                ans = ans * 10 + c - '0', c = getchar();        }        return ans;}//并查集部分int F[MAXN];//需要初始化为-1int find(int x){        if (F[x] == -1)        {                return x;        }        return F[x] = find(F[x]);}void bing(int u, int v){        int t1 = find(u);        int t2 = find(v);        if (t1 != t2)        {                F[t1] = t2;        }}//************************bool vis[MAXN];//访问标记int ancestor[MAXN];//祖先struct Edge{        int to, next;} edge[MAXN * 2];int head[MAXN], tot;void addedge(int u, int v){        edge[tot].to = v;        edge[tot].next = head[u];        head[u] = tot++;}struct Query{        int q, next;        int index;//查询编号} query[MAXQ * 2];int answer[MAXQ];//存储最后的查询结果，下标0~Q-1int finalfather[MAXN];void getfather(int x, int pre, int aim){        finalfather[x] = aim;        for (int i = head[x]; i != -1; i = edge[i].next)        {                int v = edge[i].to;                if (v == pre)                {                        continue;                }                getfather(v, x, aim);        }}int h[MAXQ];int tt;int Q;void add_query(int u, int v, int index){        query[tt].q = v;        query[tt].next = h[u];        query[tt].index = index;        h[u] = tt++;        query[tt].q = u;        query[tt].next = h[v];        query[tt].index = index;        h[v] = tt++;}void init(){        tot = 0;        memset(head, -1, sizeof(head));        tt = 0;        memset(h, -1, sizeof(h));        memset(vis, false, sizeof(vis));        memset(F, -1, sizeof(F));        memset(ancestor, 0, sizeof(ancestor));}void LCA(int u){        ancestor[u] = u;        vis[u] = true;        for (int i = head[u]; i != -1; i = edge[i].next)        {                int v = edge[i].to;                if (vis[v])                {                        continue;                }                LCA(v);                bing(u, v);                ancestor[find(u)] = u;        }        for (int i = h[u]; i != -1; i = query[i].next)        {                int v = query[i].q;                if (vis[v])                {                        //cout << " " << u << " " << v << " " << find(u) << " " << find(v)<
       
         mp;map
        
          mpback;int Qflag[MAXQ];int pop = 0;string anser[MAXN];string from, to;void getnum(string x){        if (mp[x])        {                return ;        }        mp[x] = ++pop;        mpback[pop] = x;        return ;}bool flag[MAXN];int main(){        int n;        int u, v, k;        while (scanf("%d", &n) == 1)        {                for (int i = 0; i < MAXN; i++)                {                        anser[i] = "";                }                init();                memset(flag, false, sizeof(flag));                for (int i = 1; i <= n; i++)                {                        cin >> from >> to;                        getnum(from);                        getnum(to);                        //cout << mp[from] << "   " << mp[to] << endl;                        flag[mp[to]] = true;                        addedge(mp[from], mp[to]);                        addedge(mp[to], mp[from]);                }                Q = readint();                for (int i = 0; i < Q; i++)                {                        //                        u = readint();                        //                        v = readint();                        //                        add_query(u, v, i);                        cin >> from >> to;                        if (from == to)                        {                                anser[i] = from;                        }                        else                        {                                if (mp.find(from) == mp.end() || mp.find(to) == mp.end())                                {                                        anser[i] = "-1";                                }                                else                                {                                        add_query(mp[from], mp[to], i);                                }                        }                }                int root;                for (int i = 1; i <= pop; i++)                {                        if (!flag[i])                        {                                getfather(i, -1, i);                        }                }                for (int i = 1; i <= pop; i++)                        if (!flag[i])                        {                                root = i;                                LCA(root);                        }                for (int i = 0; i < Q; i++)                {                        if (anser[i] != "")                        {                                cout << anser[i] << endl;                        }                        else                        {                                if (answer[i] == -1)                                {                                        cout << -1 << endl;                                }                                else                                {                                        cout << mpback[answer[i]] << endl;                                }                        }                }        }        return 0;}
        
       
      

在线:

①倍增

/* Huyyt */#include 
      
       using namespace std;const int maxn = 405;  //点的最大值const int maxl = 25; //深度的最大值typedef struct{        int from, to, w;} edge; //这个结构体用来存储边vector
       
         edges;vector
        
          G[maxn];//保存边的数组int grand[maxn][maxl];  //x向上跳2^i次方的节点，x到他上面祖先2^i次方的距离int gw[maxn][maxl];   //维护距离的数组//int gwmax[maxn][maxl]; //维护边权最大值的数组int depth[maxn];//深度int root;int n, m;int N; //N的意思是最多能跳几层map
         
           mp;map
          
            mpback;int pop = 0;string from, to;void addedge(int x, int y, int w)  //把边保存起来的函数{        edge a = {x, y, w}, b = {y, x, w};        edges.push_back(a);        edges.push_back(b);        G[x].push_back(edges.size() - 2);        G[y].push_back(edges.size() - 1);}void dfs(int x)//dfs建图{        for (int i = 1; i <= N; i++) //第一个几点就全部都是0,第二个节点就有变化了,不理解的话建议复制代码输出下这些数组        {                grand[x][i] = grand[grand[x][i - 1]][i - 1];  //倍增 2^i=2^(i-1)+2^(i-1)                gw[x][i] = gw[x][i - 1] + gw[grand[x][i - 1]][i - 1]; //维护一个距离数组                //gwmax[x][i]=max(gwmax[x][i-1],gw[grand[x][i-1]][i-1]);                // if(grand[x][i]==0) break;        }        for (int i = 0; i < G[x].size(); i++)        {                edge  e = edges[G[x][i]];                if (e.to != grand[x][0]) //这里我们保存的是双向边所以与他相连的边不是他父亲就是他儿子父亲的话就不能执行，不然就死循环了。                {                        depth[e.to] = depth[x] + 1; //他儿子的深度等于他爸爸的加1                        grand[e.to][0] = x; //与x相连那个节点的父亲等于x                        gw[e.to][0] = e.w; //与x相连那个节点的距离等于这条边的距离                        //gwmax[e.to][0]=e.w;                        dfs(e.to);//深搜往下面建                }        }}void Init(){        //n为节点个数        N = floor(log(maxn + 0.0) / log(2.0));//最多能跳的2^i祖先        depth[root] = 0; //根结点的祖先不存在，用-1表示        depth[0] = -1;        memset(grand, 0, sizeof(grand));        //memset(gw, 0, sizeof(gw));        dfs(root);//以根节点建树}int lca(int a, int b){        if (depth[a] > depth[b])        {                swap(a, b);        //保证a在b上面，便于计算        }        int ans = 0;        for (int i = N; i >= 0; i--) //类似于二进制拆分，从大到小尝试        {                if (depth[a] < depth[b] && depth[grand[b][i]] >= depth[a]) //a在b下面且b向上跳后不会到a上面                {                        ans += gw[b][i], b = grand[b][i];        //先把深度较大的b往上跳                }        }        if (a == b)        {                return a;        }        for (int j = N; j >= 0; j--) //在同一高度了,他们一起向上跳,跳他们不相同节点，当全都跳完之后grand【a】【0】就是lca,上面有解释哈。        {                if (grand[a][j] != grand[b][j])                {                        ans += gw[a][j];                        ans += gw[b][j];                        a = grand[a][j];                        b = grand[b][j];                }        }        if (a != b) //a等于b的情况就是上面土色字体的那种情况        {                ans += gw[a][0], ans += gw[b][0];        }        if (grand[a][0] == 0 && grand[b][0] == 0 && a != b)        {                return -1;        }        return grand[a][0];}void getnum(string x){        if (mp[x])        {                return ;        }        mp[x] = ++pop;        mpback[pop] = x;        return ;}int in[maxn];int main(){        N = floor(log(maxn + 0.0) / log(2.0));        depth[0] = -1;        cin >> n;        for (int i = 1; i <= n; i++)        {                cin >> from >> to;                getnum(from);                getnum(to);                //cout << mp[from] << " " << mp[to] << endl;                addedge(mp[from], mp[to], 1);                in[mp[to]]++;        }        for (int i = 1; i <= pop; i++)        {                if (in[i] == 0)                {                        root = i;                        dfs(root);                }        }        cin >> m;        for (int i = 1; i <= m; i++)        {                cin >> from >> to;                if (from == to)                {                        cout << from << endl;                }                else                {                        if (mp.find(from) == mp.end() || mp.find(to) == mp.end())                        {                                cout << -1 << endl;                        }                        else                        {                                int aim = lca(mp[from], mp[to]);                                if (aim == -1)                                {                                        cout << -1 << endl;                                }                                else                                {                                        cout << mpback[aim] << endl;                                }                        }                }        }}
          
         
        
       
      

hihocoder 1067   单树不带权LCA

离线:

①Tarjan

#include
      
       using namespace std;const int MAXN = 200010;const int MAXQ = 100010;//查询数的最大值inline int readint(){        char c = getchar();        int ans = 0;        while (c < '0' || c > '9')        {                c = getchar();        }        while (c >= '0' && c <= '9')        {                ans = ans * 10 + c - '0', c = getchar();        }        return ans;}//并查集部分int F[MAXN];//需要初始化为-1int find(int x){        if (F[x] == -1)        {                return x;        }        return F[x] = find(F[x]);}void bing(int u, int v){        int t1 = find(u);        int t2 = find(v);        if (t1 != t2)        {                F[t1] = t2;        }}//************************bool vis[MAXN];//访问标记int ancestor[MAXN];//祖先struct Edge{        int to, next;} edge[MAXN * 2];int head[MAXN], tot;void addedge(int u, int v){        edge[tot].to = v;        edge[tot].next = head[u];        head[u] = tot++;}struct Query{        int q, next;        int index;//查询编号} query[MAXQ * 2];int answer[MAXQ];//存储最后的查询结果，下标0~Q-1int h[MAXQ];int tt;int Q;void add_query(int u, int v, int index){        query[tt].q = v;        query[tt].next = h[u];        query[tt].index = index;        h[u] = tt++;        query[tt].q = u;        query[tt].next = h[v];        query[tt].index = index;        h[v] = tt++;}void init(){        tot = 0;        memset(head, -1, sizeof(head));        tt = 0;        memset(h, -1, sizeof(h));        memset(vis, false, sizeof(vis));        memset(F, -1, sizeof(F));        memset(ancestor, 0, sizeof(ancestor));}void LCA(int u){        ancestor[u] = u;        vis[u] = true;        for (int i = head[u]; i != -1; i = edge[i].next)        {                int v = edge[i].to;                if (vis[v])                {                        continue;                }                LCA(v);                bing(u, v);                ancestor[find(u)] = u;        }        for (int i = h[u]; i != -1; i = query[i].next)        {                int v = query[i].q;                if (vis[v])                {                        answer[query[i].index] = ancestor[find(v)];                }        }}map
       
         mp;map
        
          mpback;int pop = 0;string from, to;void getnum(string x){        if (mp[x])        {                return ;        }        mp[x] = ++pop;        mpback[pop] = x;        return ;}bool flag[MAXN];int Count_num[MAXN];int main(){        //freopen("in.txt","r",stdin);        //freopen("out.txt","w",stdout);        int n;        int u, v, k;        while (scanf("%d", &n) == 1)        {                init();                memset(flag, false, sizeof(flag));                for (int i = 1; i <= n; i++)                {                        cin >> from >> to;                        getnum(from);                        getnum(to);                        flag[mp[to]]=true;                        addedge(mp[from],mp[to]);                        addedge(mp[to],mp[from]);                }                Q = readint();                for (int i = 0; i < Q; i++)                {                        cin >> from >> to;                        add_query(mp[from],mp[to], i);                }                int root;                for (int i = 1; i <= n; i++)                        if (!flag[i])                        {                                root = i;                                break;                        }                LCA(root);                memset(Count_num, 0, sizeof(Count_num));                for (int i = 0; i < Q; i++)                {                        cout<
         
          <
         
        
       
      

 在线:

①倍增

/* Huyyt */#include 
      
       using namespace std;const int maxn = 200005;  //点的最大值const int maxl = 25; //深度的最大值typedef struct{        int from, to, w;} edge; //这个结构体用来存储边vector
       
         edges;vector
        
          G[maxn];//保存边的数组int grand[maxn][maxl];  //x向上跳2^i次方的节点，x到他上面祖先2^i次方的距离int gw[maxn][maxl];   //维护距离的数组//int gwmax[maxn][maxl]; //维护边权最大值的数组int depth[maxn];//深度int root;int n, m;int N; //N的意思是最多能跳几层map
         
           mp;map
          
            mpback;int pop = 0;string from, to;void addedge(int x, int y, int w)  //把边保存起来的函数{        edge a = {x, y, w}, b = {y, x, w};        edges.push_back(a);        edges.push_back(b);        G[x].push_back(edges.size() - 2);        G[y].push_back(edges.size() - 1);}void dfs(int x)//dfs建图{        for (int i = 1; i <= N; i++) //第一个几点就全部都是0,第二个节点就有变化了,不理解的话建议复制代码输出下这些数组        {                grand[x][i] = grand[grand[x][i - 1]][i - 1];  //倍增 2^i=2^(i-1)+2^(i-1)                gw[x][i] = gw[x][i - 1] + gw[grand[x][i - 1]][i - 1]; //维护一个距离数组                //gwmax[x][i]=max(gwmax[x][i-1],gw[grand[x][i-1]][i-1]);                // if(grand[x][i]==0) break;        }        for (int i = 0; i < G[x].size(); i++)        {                edge  e = edges[G[x][i]];                if (e.to != grand[x][0]) //这里我们保存的是双向边所以与他相连的边不是他父亲就是他儿子父亲的话就不能执行，不然就死循环了。                {                        depth[e.to] = depth[x] + 1; //他儿子的深度等于他爸爸的加1                        grand[e.to][0] = x; //与x相连那个节点的父亲等于x                        gw[e.to][0] = e.w; //与x相连那个节点的距离等于这条边的距离                        //gwmax[e.to][0]=e.w;                        dfs(e.to);//深搜往下面建                }        }}void Init(){        //n为节点个数        N = floor(log(pop + 0.0) / log(2.0));//最多能跳的2^i祖先        depth[root] = 0; //根结点的祖先不存在，用-1表示        depth[0] = -1;        memset(grand, 0, sizeof(grand));        memset(gw, 0, sizeof(gw));        dfs(root);//以根节点建树}int lca(int a, int b){        if (depth[a] > depth[b])        {                swap(a, b);        //保证a在b上面，便于计算        }        int ans = 0;        for (int i = N; i >= 0; i--) //类似于二进制拆分，从大到小尝试        {                if (depth[a] < depth[b] && depth[grand[b][i]] >= depth[a]) //a在b下面且b向上跳后不会到a上面                {                        ans += gw[b][i], b = grand[b][i];        //先把深度较大的b往上跳                }        }        if (a == b)        {                return a;        }        for (int j = N; j >= 0; j--) //在同一高度了,他们一起向上跳,跳他们不相同节点，当全都跳完之后grand【a】【0】就是lca,上面有解释哈。        {                if (grand[a][j] != grand[b][j])                {                        ans += gw[a][j];                        ans += gw[b][j];                        a = grand[a][j];                        b = grand[b][j];                }        }        if (a != b) //a等于b的情况就是上面土色字体的那种情况        {                ans += gw[a][0], ans += gw[b][0];        }        return grand[a][0];}void getnum(string x){        if (mp[x])        {                return ;        }        mp[x] = ++pop;        mpback[pop] = x;        return ;}int main(){        root = 1;        cin >> n;        for (int i = 1; i <= n; i++)        {                cin >> from >> to;                getnum(from);                getnum(to);                //cout << mp[from] << " " << mp[to] << endl;                addedge(mp[from], mp[to], 1);        }        Init();        cin >> m;        for (int i = 1; i <= m; i++)        {                cin >> from >> to;                //getnum(from), getnum(to);                cout << mpback[lca(mp[from], mp[to])] << endl;        }}
          
         
        
       
      

hihocoder 1069  在线单树不带权LCA

①倍增

/* Huyyt */#include 
      
       using namespace std;const int maxn = 200005;  //点的最大值const int maxl = 25; //深度的最大值typedef struct{        int from, to, w;} edge; //这个结构体用来存储边vector
       
         edges;vector
        
          G[maxn];//保存边的数组int grand[maxn][maxl];  //x向上跳2^i次方的节点，x到他上面祖先2^i次方的距离int gw[maxn][maxl];   //维护距离的数组//int gwmax[maxn][maxl]; //维护边权最大值的数组int depth[maxn];//深度int root;int n, m;int N; //N的意思是最多能跳几层map
         
           mp;map
          
            mpback;int pop = 0;string from, to;void addedge(int x, int y, int w)  //把边保存起来的函数{        edge a = {x, y, w}, b = {y, x, w};        edges.push_back(a);        edges.push_back(b);        G[x].push_back(edges.size() - 2);        G[y].push_back(edges.size() - 1);}void dfs(int x)//dfs建图{        for (int i = 1; i <= N; i++) //第一个几点就全部都是0,第二个节点就有变化了,不理解的话建议复制代码输出下这些数组        {                grand[x][i] = grand[grand[x][i - 1]][i - 1];  //倍增 2^i=2^(i-1)+2^(i-1)                gw[x][i] = gw[x][i - 1] + gw[grand[x][i - 1]][i - 1]; //维护一个距离数组                //gwmax[x][i]=max(gwmax[x][i-1],gw[grand[x][i-1]][i-1]);                // if(grand[x][i]==0) break;        }        for (int i = 0; i < G[x].size(); i++)        {                edge  e = edges[G[x][i]];                if (e.to != grand[x][0]) //这里我们保存的是双向边所以与他相连的边不是他父亲就是他儿子父亲的话就不能执行，不然就死循环了。                {                        depth[e.to] = depth[x] + 1; //他儿子的深度等于他爸爸的加1                        grand[e.to][0] = x; //与x相连那个节点的父亲等于x                        gw[e.to][0] = e.w; //与x相连那个节点的距离等于这条边的距离                        //gwmax[e.to][0]=e.w;                        dfs(e.to);//深搜往下面建                }        }}void Init(){        //n为节点个数        N = floor(log(pop + 0.0) / log(2.0));//最多能跳的2^i祖先        depth[root] = 0; //根结点的祖先不存在，用-1表示        depth[0] = -1;        memset(grand, 0, sizeof(grand));        memset(gw, 0, sizeof(gw));        dfs(root);//以根节点建树}int lca(int a, int b){        if (depth[a] > depth[b])        {                swap(a, b);        //保证a在b上面，便于计算        }        int ans = 0;        for (int i = N; i >= 0; i--) //类似于二进制拆分，从大到小尝试        {                if (depth[a] < depth[b] && depth[grand[b][i]] >= depth[a]) //a在b下面且b向上跳后不会到a上面                {                        ans += gw[b][i], b = grand[b][i];        //先把深度较大的b往上跳                }        }        if (a == b)        {                return a;        }        for (int j = N; j >= 0; j--) //在同一高度了,他们一起向上跳,跳他们不相同节点，当全都跳完之后grand【a】【0】就是lca,上面有解释哈。        {                if (grand[a][j] != grand[b][j])                {                        ans += gw[a][j];                        ans += gw[b][j];                        a = grand[a][j];                        b = grand[b][j];                }        }        if (a != b) //a等于b的情况就是上面土色字体的那种情况        {                ans += gw[a][0], ans += gw[b][0];        }        return grand[a][0];}void getnum(string x){        if (mp[x])        {                return ;        }        mp[x] = ++pop;        mpback[pop] = x;        return ;}int main(){        root = 1;        cin >> n;        for (int i = 1; i <= n; i++)        {                cin >> from >> to;                getnum(from);                getnum(to);                //cout << mp[from] << " " << mp[to] << endl;                addedge(mp[from], mp[to], 1);        }        Init();        cin >> m;        for (int i = 1; i <= m; i++)        {                cin >> from >> to;                //getnum(from), getnum(to);                cout << mpback[lca(mp[from], mp[to])] << endl;        }}
          
         
        
       
      

codevs4605  在线单树不带权LCA

①倍增

/* Huyyt */#include 
      
       using namespace std;const int maxn = 200005;  //点的最大值const int maxl = 25; //深度的最大值typedef struct{        int from, to, w;} edge; //这个结构体用来存储边vector
       
         edges;vector
        
          G[maxn];//保存边的数组int grand[maxn][maxl];  //x向上跳2^i次方的节点，x到他上面祖先2^i次方的距离int gw[maxn][maxl];   //维护距离的数组//int gwmax[maxn][maxl]; //维护边权最大值的数组int depth[maxn];//深度int root;int from, to;int n, m;int N; //N的意思是最多能跳几层void addedge(int x, int y, int w)  //把边保存起来的函数{        edge a = {x, y, w}, b = {y, x, w};        edges.push_back(a);        edges.push_back(b);        G[x].push_back(edges.size() - 2);        G[y].push_back(edges.size() - 1);}void dfs(int x)//dfs建图{        for (int i = 1; i <= N; i++) //第一个几点就全部都是0,第二个节点就有变化了,不理解的话建议复制代码输出下这些数组        {                grand[x][i] = grand[grand[x][i - 1]][i - 1];  //倍增 2^i=2^(i-1)+2^(i-1)                gw[x][i] = gw[x][i - 1] + gw[grand[x][i - 1]][i - 1]; //维护一个距离数组                //gwmax[x][i]=max(gwmax[x][i-1],gw[grand[x][i-1]][i-1]);                // if(grand[x][i]==0) break;        }        for (int i = 0; i < G[x].size(); i++)        {                edge  e = edges[G[x][i]];                if (e.to != grand[x][0]) //这里我们保存的是双向边所以与他相连的边不是他父亲就是他儿子父亲的话就不能执行，不然就死循环了。                {                        depth[e.to] = depth[x] + 1; //他儿子的深度等于他爸爸的加1                        grand[e.to][0] = x; //与x相连那个节点的父亲等于x                        gw[e.to][0] = e.w; //与x相连那个节点的距离等于这条边的距离                        //gwmax[e.to][0]=e.w;                        dfs(e.to);//深搜往下面建                }        }}void Init(){        //n为节点个数        N = floor(log(n + 0.0) / log(2.0));//最多能跳的2^i祖先        depth[root] = 0; //根结点的祖先不存在，用-1表示        depth[0] = -1;        memset(grand, 0, sizeof(grand));        memset(gw, 0, sizeof(gw));        dfs(root);//以根节点建树}int lca(int a, int b){        if (depth[a] > depth[b])        {                swap(a, b);        //保证a在b上面，便于计算        }        int ans = 0;        for (int i = N; i >= 0; i--) //类似于二进制拆分，从大到小尝试        {                if (depth[a] < depth[b] && depth[grand[b][i]] >= depth[a]) //a在b下面且b向上跳后不会到a上面                {                        ans += gw[b][i], b = grand[b][i];        //先把深度较大的b往上跳                }        }        if (a == b)        {                return a;        }        for (int j = N; j >= 0; j--) //在同一高度了,他们一起向上跳,跳他们不相同节点，当全都跳完之后grand【a】【0】就是lca,上面有解释哈。        {                if (grand[a][j] != grand[b][j])                {                        ans += gw[a][j];                        ans += gw[b][j];                        a = grand[a][j];                        b = grand[b][j];                }        }        if (a != b) //a等于b的情况就是上面土色字体的那种情况        {                ans += gw[a][0], ans += gw[b][0];        }        return grand[a][0];}int main(){        root = 1;        cin >> n;        for (int i = 1; i <= n; i++)        {                cin >> to;                if (to == 0)                {                        root = i;                        continue;                }                addedge(to, i, 1);        }        Init();        cin >> m;        int anser = 0;        for (int i = 1; i <= m; i++)        {                cin >> from >> to;                from ^= anser;                to ^= anser;                anser = lca(from, to);                cout << anser << endl;        }}
        
       
      

②ST

/*Huyyt*/#include
      
       #define mem(a,b) memset(a,b,sizeof(a))#define pb push_backusing namespace std;typedef long long ll;typedef unsigned long long ull;const int mod = 1e9 + 7;const int gakki = 5 + 2 + 1 + 19880611 + 1e9;const int MAXN = 2e5 + 5, MAXM = 2e5 + 5;int to[MAXM << 1], nxt[MAXM << 1], Head[MAXN], tot = 1;inline void addedge(int u, int v){        to[++tot] = v;        nxt[tot] = Head[u];        Head[u] = tot;}int depth[2 * MAXN], ver[2 * MAXN], first[MAXN], dfs_clock = 0;int dp[MAXN][25];void dfs(int x, int fa, int deep){        ver[++dfs_clock] = x;        first[x] = dfs_clock;        depth[dfs_clock] = deep;        for (int i = Head[x]; i; i = nxt[i])        {                int v = to[i];                if (v != fa)                {                        dfs(v, x, deep + 1);                        ver[++dfs_clock] = x;                        depth[dfs_clock] = deep;                }        }}void ST(int n){        for (int i = 1; i <= n; i++)        {                dp[i][0] = i;        }        for (int j = 1; (1 << j) <= n; j++)        {                for (int i = 1; i + (1 << j) - 1 <= n; i++)                {                        dp[i][j] = depth[dp[i][j - 1]] < depth[dp[i + (1 << (j - 1))][j - 1]] ? dp[i][j - 1] : dp[i + (1 << (j - 1))][j - 1];                }        }}int RMQ(int l, int r){        int k = (int)(log((double)(r-l+1)) / log(2.0));        return depth[dp[l][k]] < depth[dp[r - (1 << k) + 1][k]] ? dp[l][k] : dp[r - (1 << k) + 1][k];}int LCA(int u, int v){        int a = first[u], b = first[v];        if (a > b)        {                swap(a, b);        }        int res = RMQ(a, b);        return ver[res];}int main(){        ios_base::sync_with_stdio(0);        cin.tie(0);        int root;        int n, m, u, v;        cin >> n;        for (int i = 1; i <= n; i++)        {                cin >> u;                if (u == 0)                {                        root = i;                        continue;                }                addedge(i, u), addedge(u, i);        }        dfs(root, 0, 1);        ST(dfs_clock);        int anser = 0;        cin >> m;        for (int i = 1; i <= m; i++)        {                cin >> u >> v;                u = u ^ anser;                v = v ^ anser;                anser = LCA(u, v);                cout << anser << endl;        }        return 0;}
      

 POJ1470   大量输入5e5询问LCA

①Tarjan

#include
      
       using namespace std;const int MAXN = 1010;const int MAXQ = 500010;//查询数的最大值inline int readint(){        char c = getchar();        int ans = 0;        while (c < '0' || c > '9')        {                c = getchar();        }        while (c >= '0' && c <= '9')        {                ans = ans * 10 + c - '0', c = getchar();        }        return ans;}//并查集部分int F[MAXN];//需要初始化为-1int find(int x){        if (F[x] == -1)        {                return x;        }        return F[x] = find(F[x]);}void bing(int u, int v){        int t1 = find(u);        int t2 = find(v);        if (t1 != t2)        {                F[t1] = t2;        }}//************************bool vis[MAXN];//访问标记int ancestor[MAXN];//祖先struct Edge{        int to, next;} edge[MAXN * 2];int head[MAXN], tot;void addedge(int u, int v){        edge[tot].to = v;        edge[tot].next = head[u];        head[u] = tot++;}struct Query{        int q, next;        int index;//查询编号} query[MAXQ * 2];int answer[MAXQ];//存储最后的查询结果，下标0~Q-1int h[MAXQ];int tt;int Q;void add_query(int u, int v, int index){        query[tt].q = v;        query[tt].next = h[u];        query[tt].index = index;        h[u] = tt++;        query[tt].q = u;        query[tt].next = h[v];        query[tt].index = index;        h[v] = tt++;}void init(){        tot = 0;        memset(head, -1, sizeof(head));        tt = 0;        memset(h, -1, sizeof(h));        memset(vis, false, sizeof(vis));        memset(F, -1, sizeof(F));        memset(ancestor, 0, sizeof(ancestor));}void LCA(int u){        ancestor[u] = u;        vis[u] = true;        for (int i = head[u]; i != -1; i = edge[i].next)        {                int v = edge[i].to;                if (vis[v])                {                        continue;                }                LCA(v);                bing(u, v);                ancestor[find(u)] = u;        }        for (int i = h[u]; i != -1; i = query[i].next)        {                int v = query[i].q;                if (vis[v])                {                        answer[query[i].index] = ancestor[find(v)];                }        }}bool flag[MAXN];int Count_num[MAXN];int main(){        //freopen("in.txt","r",stdin);        //freopen("out.txt","w",stdout);        int n;        int u, v, k;        while (scanf("%d", &n) == 1)        {                init();                memset(flag, false, sizeof(flag));                for (int i = 1; i <= n; i++)                {                        u = readint();                        k = readint();                        while (k--)                        {                                v = readint();                                flag[v] = true;                                addedge(u, v);                                addedge(v, u);                        }                }                Q = readint();                for (int i = 0; i < Q; i++)                {                        u = readint();                        v = readint();                        add_query(u, v, i);                }                int root;                for (int i = 1; i <= n; i++)                        if (!flag[i])                        {                                root = i;                                break;                        }                LCA(root);                memset(Count_num, 0, sizeof(Count_num));                for (int i = 0; i < Q; i++)                {                        Count_num[answer[i]]++;                }                for (int i = 1; i <= n; i++)                        if (Count_num[i] > 0)                        {                                printf("%d:%d\n", i, Count_num[i]);                        }        }        return 0;}
      

POJ 1330

HDU 4547

SPOJ 10628  在线第K大点(主席树+LCA) 

/*SPOJ 10628第一行两个整数N,M  1E5第二行有N个整数，其中第i个整数表示点i的权值后面N-1行每行两个整数(x,y)，表示点x到点y有一条边最后M行每行两个整数(u,v,k)，表示一组询问*//*Huyyt*/#include
      
       #define inf 0x7fffffff#define ll long long#define N 100005#define M 2000005using namespace std;inline ll read(){    ll x=0,f=1;char ch=getchar();    while(ch>'9'||ch<'0'){
    if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return x*f;}int n,m,tot,sz,cnt,ind,last;int num[N],pos[N];int v[N],tmp[N],hash[N],root[N];int ls[M],rs[M],sum[M];int deep[N],fa[N][17];struct data{
    int to,next;}e[200005];int head[N];void ins(int u,int v){e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;}void insert(int u,int v){ins(u,v);ins(v,u);}int find(int x){    int l=1,r=tot;    while(l<=r)    {        int mid=(l+r)>>1;        if(hash[mid]
       
        =0;i--)        if(fa[x][i]!=fa[y][i])            x=fa[x][i],y=fa[y][i];    if(x==y)return x;    return fa[x][0];}void update(int l,int r,int x,int &y,int num){    y=++sz;    sum[y]=sum[x]+1;    if(l==r)return;    ls[y]=ls[x];rs[y]=rs[x];    int mid=(l+r)>>1;    if(num<=mid)        update(l,mid,ls[x],ls[y],num);    else update(mid+1,r,rs[x],rs[y],num);}int que(int x,int y,int rk){    int a=x,b=y,c=lca(x,y),d=fa[c][0];    a=root[pos[a]],b=root[pos[b]],c=root[pos[c]],d=root[pos[d]];    int l=1,r=tot;    while(l
        
         >1;        int tmp=sum[ls[a]]+sum[ls[b]]-sum[ls[c]]-sum[ls[d]];        if(tmp>=rk)r=mid,a=ls[a],b=ls[b],c=ls[c],d=ls[d];        else rk-=tmp,l=mid+1,a=rs[a],b=rs[b],c=rs[c],d=rs[d];    }    return hash[l];}int main(){    n=read(),m=read();    for(int i=1;i<=n;i++)        v[i]=read(),tmp[i]=v[i];    sort(tmp+1,tmp+n+1);    hash[++tot]=tmp[1];    for(int i=2;i<=n;i++)        if(tmp[i]!=tmp[i-1])hash[++tot]=tmp[i];    for(int i=1;i<=n;i++)v[i]=find(v[i]);    for(int i=1;i
        
       
      

HDU 3078  离线修改第K大点

0 a b 表示把点a的权改为b

k a b 表示求出从a到b的路径中,第K大的点权

①Tarjan

/*先用离线Tarjan把每个Query树链的LCA求出来LCA中对连接树Dfs的时候，令p[v]=u，记录v的前驱LCA结束后，对于每个Query：从u开始回溯到LCA，记录值。从v开始回溯到LCA，记录值再加上LCA这个点的值，形成一条完整树链。特判树链长度是否小于K对树链中的值，从大到小排序，取第K大即可*//*Huyyt*/#include
      
       using namespace std;#define maxn 80005int head[maxn],qhead[maxn],lag[maxn],kth[maxn],tot1,tot2,f[maxn],vis[maxn],ancestor[maxn],p[maxn];bool cmp(int a,int b) {
    return a>b;}struct Edge{    int to,next;}e[maxn*2];struct Query{    int from,to,next,idx;}q[maxn*2];void addedge(int u,int v){    e[tot1].to=v;    e[tot1].next=head[u];    head[u]=tot1++;}void addquery(int u,int v,int idx){    q[tot2].from=u;    q[tot2].to=v;    q[tot2].next=qhead[u];    q[tot2].idx=idx;    qhead[u]=tot2++;}int find(int x) {
    return x!=f[x]?f[x]=find(f[x]):x;}void Union(int u,int v){    u=find(u),v=find(v);    if(u!=v) f[v]=u;}void LCA(int u){    vis[u]=true;    f[u]=u;    for(int i=head[u];i!=-1;i=e[i].next)    {        int v=e[i].to;        if(!vis[v])        {            p[v]=u;            LCA(v);            Union(u,v);        }    }    for(int i=qhead[u];i!=-1;i=q[i].next)    {        int v=q[i].to;        if(vis[v]) ancestor[q[i].idx]=find(v);        //or storage e[i].lca=e[i^1].lca=find(v)    }}int main(){    //freopen("in.txt","r",stdin);    int T,n,m,u,v,c,cmd;    scanf("%d%d",&n,&m);    tot1=tot2=0;    memset(head,-1,sizeof(head));    memset(qhead,-1,sizeof(qhead));    memset(vis,0,sizeof(vis));    for(int i=1;i<=n;i++) scanf("%d",&lag[i]);    for(int i=0; i
       

chain; while(u!=ed) chain.push_back(lag[u]),u=p[u]; while(v!=ed) chain.push_back(lag[v]),v=p[v]; chain.push_back(lag[ed]); if(chain.size()