您的位置: 首页  >  IT文章  >  LCA统计

LCA统计

分类: IT文章 • 2023-11-07 23:42:55

读入挂

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<bits/stdc++.h>
  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<int> 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
", ans[i]);
 98                 }
 99         }
100         return 0;
101 }
//HDU2586

倍增:

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]<dep[y]) swap(x,y);
    int tmp=dep[x]-dep[y];
    for (int i=0;i<=20;i++){
        if (tmp&(1<<i)) x=f[x][i];
    }
    if (x==y) return x;
    for (int i=20;i>=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]<dep[y]) swap(x,y);
    int tmp=dep[x]-dep[y],ret=1e9;
    for (int i=0;i<=20;i++){
        if (tmp&(1<<i)) ret=min(ret,minn[x][i]),x=f[x][i];
    }
    return ret;
}

 HDU 2586  单树带权LCA

在线:

①倍增

/* Huyyt */
#include <bits/stdc++.h>
using namespace std;
const int maxn = 40001;  //点的最大值
const int maxl = 25; //深度的最大值
typedef struct
{
        int from, to, w;
} edge; //这个结构体用来存储边
vector<edge> edges;
vector<int> 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
", lca(x, y));
                }
        }
}
View Code

离线:

②Tarjan

/*Huyyt*/
#include<bits/stdc++.h>
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];//需要初始化为-1
int 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-1
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));
        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;
}
View Code

hihocoder 1062   多树不带权LCA

离线:

①Tarjan

#include<bits/stdc++.h>
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];//需要初始化为-1
int 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-1
int 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)<<endl;
                        if (finalfather[v] != finalfather[u])
                        {
                                answer[query[i].index] = -1;
                        }
                        answer[query[i].index] = ancestor[find(v)];
                }
        }
}
map<string, int> mp;
map<int, string> 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;
}
View Code

在线:

①倍增

/* Huyyt */
#include <bits/stdc++.h>
using namespace std;
const int maxn = 405;  //点的最大值
const int maxl = 25; //深度的最大值
typedef struct
{
        int from, to, w;
} edge; //这个结构体用来存储边
vector<edge> edges;
vector<int> 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<string, int> mp;
map<int, string> 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;
                                }
                        }
                }

        }
}
View Code

hihocoder 1067   单树不带权LCA

离线:

①Tarjan

#include<bits/stdc++.h>
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];//需要初始化为-1
int 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-1
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])
                {
                        answer[query[i].index] = ancestor[find(v)];
                }
        }
}
map<string, int> mp;
map<int, string> 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<<mpback[answer[i]]<<endl;
                }
        }
        return 0;
}
View Code

 在线:

①倍增

/* Huyyt */
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200005;  //点的最大值
const int maxl = 25; //深度的最大值
typedef struct
{
        int from, to, w;
} edge; //这个结构体用来存储边
vector<edge> edges;
vector<int> 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<string, int> mp;
map<int, string> 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;
        }
}
View Code

hihocoder 1069  在线单树不带权LCA

①倍增

/* Huyyt */
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200005;  //点的最大值
const int maxl = 25; //深度的最大值
typedef struct
{
        int from, to, w;
} edge; //这个结构体用来存储边
vector<edge> edges;
vector<int> 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<string, int> mp;
map<int, string> 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;
        }
}
View Code

codevs4605  在线单树不带权LCA

①倍增

/* Huyyt */
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200005;  //点的最大值
const int maxl = 25; //深度的最大值
typedef struct
{
        int from, to, w;
} edge; //这个结构体用来存储边
vector<edge> edges;
vector<int> 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;
        }
}
View Code

②ST

/*Huyyt*/
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
using 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;
}
View Code

 POJ1470   大量输入5e5询问LCA

①Tarjan

#include<bits/stdc++.h>
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];//需要初始化为-1
int 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-1
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])
                {
                        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
", i, Count_num[i]);
                        }
        }
        return 0;
}
View Code

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<bits/stdc++.h>
#define inf 0x7fffffff
#define ll long long
#define N 100005
#define M 2000005
using 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]<x)l=mid+1;
        else if(hash[mid]==x)return mid;
        else r=mid-1;
    }
}
void dfs(int x)
{
    ind++;num[ind]=x;pos[x]=ind;
    for(int i=1;i<=16;i++)
        if((1<<i)<=deep[x])fa[x][i]=fa[fa[x][i-1]][i-1];
        else break;
    for(int i=head[x];i;i=e[i].next)
        if(fa[x][0]!=e[i].to)
        {
            deep[e[i].to]=deep[x]+1;
            fa[e[i].to][0]=x;
            dfs(e[i].to);
        }
}
int lca(int x,int y)
{
    if(deep[x]<deep[y])swap(x,y);
    int t=deep[x]-deep[y];
    for(int i=0;i<=16;i++)
        if((1<<i)&t)x=fa[x][i];
    for(int i=16;i>=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<r)
    {
        int mid=(l+r)>>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<n;i++)
    {
        int u=read(),v=read();
        insert(u,v);
    }
    dfs(1);
    for(int i=1;i<=n;i++)
    {
        int t=num[i];
        update(1,tot,root[pos[fa[t][0]]],root[i],v[t]);
    }
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read(),rk=read();
        x^=last;
        last=que(x,y,rk);
        printf("%d",last);
        if(i!=m)printf("
");
    }
    return 0;
}
View Code

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<bits/stdc++.h>
using namespace std;
#define maxn 80005
int 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<n-1; i++)
    {
        scanf("%d%d",&u,&v);
        addedge(u,v);
        addedge(v,u);
    }
    for(int i=0; i<m; i++)
    {
        scanf("%d%d%d",&cmd,&u,&v);
        if(cmd==0) lag[u]=v;
        else
        {
            addquery(u,v,i);
            addquery(v,u,i);
            kth[i]=cmd;
        }
    }
    LCA(1);
    for(int i=0; i<tot2; i=i+2)
    {
        int u=q[i].from,v=q[i].to,idx=q[i].idx;
        int ed=ancestor[idx];
        vector<int> 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()<kth[idx]) {printf("invalid request!
");continue;}
        else
        {
            sort(chain.begin(),chain.end(),cmp);
            printf("%d
",chain[kth[idx]-1]);
        }
    }
}
View Code

 ②ST

/*Huyyt*/
#include<bits/stdc++.h>
using namespace std;
const int maxn=80010;
int pre[maxn],E[maxn*2],dep[maxn*2],pos[maxn],vis[maxn];
int d[maxn*2][30],val[maxn],num,path[maxn];
int N,Q;
vector<int> g[maxn];

void init()
{
    for(int i=0;i<=N;i++)g[i].clear();
    num=0;
    memset(pos,-1,sizeof(pos));
    memset(vis,0,sizeof(vis));
}

void dfs(int u,int depth)
{
    E[++num]=u,dep[num]=depth;
    if(pos[u]==-1)pos[u]=num;
    vis[u]=1;
    int len=g[u].size();
    for(int i=0;i<len;i++)
    {
        int v=g[u][i];
        if(vis[v])continue;
        pre[v]=u;
        dfs(v,depth+1);
        E[++num]=u,dep[num]=depth;
    }
}

void initRMQ(int n)
{
    for(int i=0;i<=n;i++)d[i][0]=i;
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i+(1<<j)<=n;i++)
        {
            int x=d[i][j-1],y=d[i+(1<<(j-1))][j-1];
            if(dep[x]<dep[y])d[i][j]=x;
            else d[i][j]=y;
        }
}

int LCA(int u,int v)
{
    int x=pos[u],y=pos[v];
    if(x>y)swap(x,y);
    int k=0;
    while((1<<(k+1))<=y-x+1)k++;
    int a=d[x][k],b=d[y-(1<<k)+1][k];
    if(dep[a]<dep[b])return E[a];
    else return E[b];
}

void solve(int k,int u,int v)
{
    int fa=LCA(u,v);
    int cnt=0;
    while(u!=fa){path[cnt++]=val[u];u=pre[u];}
    while(v!=fa){path[cnt++]=val[v];v=pre[v];}
    path[cnt++]=val[fa];
    sort(path,path+cnt,greater<int>());
    if(cnt<k)printf("invalid request!
");
    else printf("%d
",path[k-1]);
}

int main()
{
    while(scanf("%d%d",&N,&Q)!=EOF)
    {
        for(int i=1;i<=N;i++)scanf("%d",&val[i]);
        init();
        for(int i=1;i<N;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        dfs(1,1);
        initRMQ(num);
        while(Q--)
        {
            int k,a,b;
            scanf("%d%d%d",&k,&a,&b);
            if(!k)val[a]=b;
            else solve(k,a,b);
        }
    }
    return 0;
}
View Code 
/*Huyyt*/
#include<bits/stdc++.h>
using namespace std;
#define N 80010
int __pow[25];
int fa[N],val[N],p[N];
int node[2*N],first[N],dep[2*N],dp[2*N][25];
bool vis[N];
vector<int>e[N];

void dfs(int &index , int u ,int d , int par)
{
    ++index; vis[u] = true;
    first[u] = index; node[index] = u; dep[index] = d; fa[u] = par;
    for(int i=0; i<e[u].size(); i++)
        if(!vis[e[u][i]])
        {
            dfs(index , e[u][i] , d+1 , u);
            ++index;
            node[index] = u; dep[index] = d;
        }
}

void ST(int n)
{
    int K = (int)(log((double)n) / log(2.0));
    for(int i=1; i<=n; i++) dp[i][0] = i;
    for(int j=1; j<=K; j++)
        for(int i=1; i+__pow[j]-1 <= n ; i++)
        {
            int a = dp[i][j-1];
            int b = dp[i+__pow[j-1]][j-1];
            if(dep[a] < dep[b]) dp[i][j] = a;
            else                dp[i][j] = b;
        }
}

int RMQ(int x ,int y)
{
    int K = (int)(log((double)(y-x+1)) / log(2.0));
    int a = dp[x][K];
    int b = dp[y-__pow[K]+1][K];
    if(dep[a] < dep[b]) return a;
    else                return b;
}

int LCA(int u ,int v)
{
    int x = first[u];
    int y = first[v];
    if(x > y) swap(x,y);
    int index = RMQ(x,y);
    return node[index];
}

bool cmp(int a, int b)
{
    return a > b;
}

void path(int &index , int s , int t)
{
    while(s != t)
    {
        p[index++] = val[s];
        s = fa[s];
    }
    p[index++] = val[t];
}

void solve(int kth , int u,int v)
{
    int lca = LCA(u,v);
    int tot = 0;
    path(tot,u,lca);
    path(tot,v,lca);
    tot--;
    if(kth > tot) 
    {
        printf("invalid request!
");
        return ;
    }
    sort(p,p+tot,cmp);
    printf("%d
",p[kth-1]);
}

int main()
{
    for(int i=0; i<25; i++) __pow[i] = 1 << i;
    
    int n,q;
    scanf("%d%d",&n,&q);
    for(int i=1; i<=n; i++) scanf("%d",&val[i]);
    for(int i=1; i<n; i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    
    int tot = 0;
    memset(vis,false,sizeof(vis));
    dfs(tot,1,1,-1);
    
    ST(tot);
    while(q--)
    {
        int op;
        scanf("%d",&op);
        if(op == 0)
        {
            int x,w;
            scanf("%d%d",&x,&w);
            val[x] = w;
        }
        else
        {
            int u,v;
            scanf("%d%d",&u,&v);
            solve(op,u,v);
        }
    }
    return 0;
}
View Code

Codeforces 932D  倍增维护

给你一个有根树根的下标为1 每个节点有一个权值 根的权值为0 总共有4e5次 强制在线操作

操作1:在R节点下面加一个权值为W的新节点

操作2:询问从R开始朝根节点走 走到第一个权值不小于它的节点且经过的节点权值和不大于W的最长长度

维护两个数组 一个是father[i][j]表示在i之上 第2^j个比i权值大的点 第二个是sum[i][j]表示从i到第2^j个比i权值大的点途中经过点的权值和(不包括W[i]) 

/*Huyyt*/
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll LLmaxn = 2e18;
const int maxn = 400005;
inline long long read()
{
        char c = getchar();
        long long ans = 0;
        while (c < '0' || c > '9')
        {
                c = getchar();
        }
        while (c >= '0' && c <= '9')
        {
                ans = ans * 10 + c - '0', c = getchar();
        }
        return ans;
}
ll w[maxn];
ll father[maxn][21];
ll sum[maxn][21];
int cnt = 1;
ll last = 0;
void add(ll a, ll b)
{
        w[++cnt] = b;
        if (w[a] >= w[cnt])
        {
                father[cnt][0] = a;
        }
        else
        {
                for (int i = 20; i >= 0; i--)
                {
                        if (w[father[a][i]] < w[cnt])
                        {
                                a = father[a][i];
                        }
                }
                father[cnt][0] = father[a][0];
        }
        if (father[cnt][0] == 0)
        {
                sum[cnt][0] = LLmaxn;
        }
        else
        {
                sum[cnt][0] = w[father[cnt][0]];
        }
        for (int i = 1; i <= 20; i++)
        {
                father[cnt][i] = father[father[cnt][i - 1]][i - 1];
                if (father[cnt][i] == 0)
                {
                        sum[cnt][i] = LLmaxn;
                }
                else
                {
                        sum[cnt][i] = sum[cnt][i - 1] + sum[father[cnt][i - 1]][i - 1];
                }
        }
}
ll query(ll a, ll b)
{
        if (w[a] > b)
        {
                return 0;
        }
        b -= w[a];
        ll ans = 1;
        for (int i = 20; i >= 0; i--)
        {
                if (b >= sum[a][i])
                {
                        b -= sum[a][i];
                        ans += (1LL << i);
                        a = father[a][i];
                }
        }
        return ans;
}
void init()
{
        w[0] = LLmaxn;
        w[1] = 0;
        father[1][0] = 0;
        mem(sum[1], 0x3f);
}
ll a, b;
int main()
{
        //cout<<LLmaxn<<endl;
        init();
        int n, Q;
        int ch;
        n = read();
        for (int i = 1; i <= n; i++)
        {
                ch = read();
                a = read();
                b = read();
                a ^= last;
                b ^= last;
                if (ch == 1)
                {
                        add(a, b);
                }
                else
                {
                        last = query(a, b);
                        cout << last << endl;
                }
        }
        return 0;
}
View Code

Codeforces 980E

给你N个点 组成的一颗树 分别从1标号到N 每个点的粉丝数量为2^i个

要求是选择K个点删除 使得剩下没被删的点保持连通且剩下的粉丝数量最大

一旦某个点被删除则其不能通过且该点的粉丝数量清零

假如做法顺着做 找出需要删除那些点的话 因为要保证连通性所以删除一个点需要删除掉他所有子树的点 不好做

题目提示你K<N 所以点N是一定可以保留的 就以N为根倍增预处理祖先 倒着做 找出不需要删除的点即可

/* Huyyt */
#include <bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define mkp(a,b) make_pair(a,b)
#define pb push_back
using namespace std;
typedef long long ll;
const long long mod = 1e9 + 7;
const int N = 1e6 + 5;
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;
}
vector<int> tree[N];
bool check[N];
int father[N][21];
int deep[N];
void dfs(int x, int level)
{
        for (int i = 0; father[father[x][i]][i]; i++)
        {
                father[x][i + 1] = father[father[x][i]][i];
        }
        deep[x] = level;
        for (int i = 0; i < tree[x].size(); i++)
        {
                int to = tree[x][i];
                if (to == father[x][0])
                {
                        continue;
                }
                father[to][0] = x;
                dfs(to, level + 1);
        }
}
int main()
{
        int n, k;
        n = readint(), k = readint();
        int u, v;
        for (int i = 1; i < n; i++)
        {
                u = readint(),v = readint();
                tree[u].pb(v);
                tree[v].pb(u);
        }
        k = n - k;
        k--, check[n] = 1;
        dfs(n, 1);
        for (int i = n - 1; i >= 1 && k; i--)
        {
                int aim = -1;
                int now = i;
                if (check[i])
                {
                        continue;
                }
                for (int j = 20; j >= 0; j--)
                {
                        if (father[now][j] == 0 || check[father[now][j]])
                        {
                                continue;
                        }
                        now = father[now][j];
                }
                if (deep[i] - deep[now] + 1 <= k)
                {
                        now = i;
                        while (now != 0 && !check[now])
                        {
                                check[now] = 1;
                                k--;
                                now = father[now][0];
                        }
                }
        }
        for (int i = 1; i <= n - 1; i++)
        {
                if (!check[i])
                {
                        cout << i << " ";
                }
        }
        return 0;
}
View Code

相关推荐