2013-team5/network-LCA

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
/*
    LCA
   O(NLogN-LogN)
*/

const int maxN = 50100;

struct edge
{
        int v, next;
}g[maxN << 1];

int vect[maxN], d[maxN], f[maxN][20], n, Q, tot;
bool vis[maxN];

void add(int u, int v)
{
        g[++tot].v = v;
        g[tot].next = vect[u];
        vect[u] = tot;
}

void dfs(int dep, int u, int fa){
        vis[u] = true;
        d[u] = dep;
        f[u][0] = fa;
        for(int tt = vect[u]; tt; tt = g[tt].next){
                int v = g[tt].v;
                if (not vis[v]) dfs(dep + 1, v, u);
        }
}

void gao()
{
    //log is very slow!
        for (int j = 1; j <= log(n) / log(2); j++){
                for (int i = 1; i <= n; i++){
                        f[i][j] = f[f[i][j - 1]][j - 1];
                }
        }
}

int query(int x, int y)
{
        int delta;
        while(d[x] < d[y]){
                delta = d[y] - d[x];
                for (int i = 0; ; i++)
                        if (1 << (i + 1) > delta){
                                y = f[y][i];
                                break;
                        }
        }

        while(d[x] > d[y]){
                delta = d[x] - d[y];
                for (int i = 0; ; i++)
                        if (1 << (i + 1) > delta){
                                x = f[x][i];
                                break;
                        }
        }

        while(x != y){
                for (int i = 0; ; i++)
                        if (f[x][i + 1] == f[y][i + 1]){
                                x = f[x][i];
                                y = f[y][i];
                                break;
                        }
        }
        return x;
}
}}}

/*
    LCA
   O(NLogN-LogN)
*/
const int maxN = 50100;
struct edge
{
        int v, next;
}g[maxN << 1];
int vect[maxN], d[maxN], f[maxN][20], n, Q, tot;
bool vis[maxN];
void add(int u, int v)
{
        g[++tot].v = v;
        g[tot].next = vect[u];
        vect[u] = tot;
}
void dfs(int dep, int u, int fa){
        vis[u] = true;
        d[u] = dep;
        f[u][0] = fa;
        for(int tt = vect[u]; tt; tt = g[tt].next){
                int v = g[tt].v;
                if (not vis[v]) dfs(dep + 1, v, u);
        }
}
void gao()
{
    //log is very slow!
        for (int j = 1; j <= log(n) / log(2); j++){
                for (int i = 1; i <= n; i++){
                        f[i][j] = f[f[i][j - 1]][j - 1];
                }
        }
}
int query(int x, int y)
{
        int delta;
        while(d[x] < d[y]){
                delta = d[y] - d[x];
                for (int i = 0; ; i++)
                        if (1 << (i + 1) > delta){
                                y = f[y][i];
                                break;
                        }
        }
        while(d[x] > d[y]){
                delta = d[x] - d[y];
                for (int i = 0; ; i++)
                        if (1 << (i + 1) > delta){
                                x = f[x][i];
                                break;
                        }
        }
        while(x != y){
                for (int i = 0; ; i++)
                        if (f[x][i + 1] == f[y][i + 1]){
                                x = f[x][i];
                                y = f[y][i];
                                break;
                        }
        }
        return x;
}