倍增 get！

A4paper · 2018-05-13 21:19:23 · 个人记录

这里，我用的是倍增求LCA

模板：

传送门

struct node
{
    int to,next;
}tree[2*MAXN];

int head[MAXN],deep[MAXN],f[MAXN][21];
int n,m,cnt,root;

void add(int u, int v)
{
    tree[++cnt] = (node){v,head[u]};
    head[u] = cnt;
}

void dfs(int u, int fa)
{
    f[u][0] = fa;
    deep[u] = deep[fa]+1;
    for(int k=head[u];k;k=tree[k].next)
    {
        int v = tree[k].to;
        if(v == fa) continue;
        dfs(v,u);
    }  
}

int LCA(int a,int b)
{
    if(deep[a] > deep[b])    swap(a,b);
    for(int i=20;i>=0;i--)
        if(deep[a] <= deep[b]-(1<<i))
            b = f[b][i];
    if(a == b)  return a;
    for(int i=20;i>=0;i--)
    {
        if(f[a][i] == f[b][i])    continue;
        a = f[a][i];
        b = f[b][i];
    }
    return f[a][0];
}

int main()
{
    scanf("%d%d%d",&n,&m,&root);
    for(int i=1,u,v;i<n;i++)
    {
        scanf ("%d%d",&u,&v);
        add(u,v);   add(v,u);
    }
    deep[root] = 1;
    dfs(root,0);
    for(int i=1;i<=20;i++)
        for(int j=1;j<=n;j++)
            f[j][i] = f[f[j][i-1]][i-1];
    for(int i=1,a,b;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        printf("%d\n",LCA(a,b));
    }
    return 0;
}

提高：

传送门

int a,b,c,ans;
int n,cnt,dep,wid,flag;
int head[105],wide[105],vis[105];
int p[205][205];

struct node{
    int L,R;
    int deep;
}tree[405];

struct Node{
    int to,next;
}map [405];

void add(int u, int v){
    map[++cnt] = (Node){v,head[u]};
    head[u] = cnt; 
}

void buildtree(int u, int fa)
{
    tree[u].deep = tree[fa].deep+1;
    if(tree[u].deep > dep)  dep = tree[u].deep;
    wide[tree[u].deep]++;
    for(int k=head[u];k;k=map[k].next)
    {
int v = map[k].to;
        if(v==fa || vis[v]) continue;
        if(tree[u].L)   tree[u].R = v;
        else            tree[u].L = v;
        vis[v] = 1;
        buildtree(v,u);
    }
}

void dfs2(int u, int fa)
{
    p[u][0] = fa;
    for(int i=1;(1<<i)<=tree[u].deep;i++)   p[u][i] = p[p[u][i-1]][i-1];
    if(tree[u].L)   dfs2(tree[u].L,u);
    if(tree[u].R)   dfs2(tree[u].R,u);
}

int LCA(int a, int b)
{
    if(tree[a].deep > tree[b].deep) swap(a,b);
    for(int i=7;i>=0;i--)
        if(tree[a].deep <= tree[b].deep-(1<<i)) b = p[b][i];
    if(a == b)  return a;
    for(int i=7;i>=0;i--)
    {
        if(p[a][i] == p[b][i])  continue;
        a = p[a][i];
        b = p[b][i];
    }
    return p[a][0];
}

int main(void)
{
    cin >> n;
    for(int i=1,u,v;i<n;i++)
    {
        cin >> u >> v;
        add(u,v);
        add(v,u);
    }
    buildtree(1,0);
    dfs2(1,0);
    for(int i=1;i<=n;i++)
        if(wide[i] > wid)   wid = wide[i];
    cin >> a >> b;
    c = LCA(a,b);
    ans = 2*(tree[a].deep-tree[c].deep)+tree[b].deep-tree[c].deep;
    cout << dep << endl << wid << endl << ans << endl;
    return 0;
}