LCA倍增

优质博客推荐

hdu6115

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
const int inf=0x3f3f3f3f;
#define mem(a,b) memset(a,b,sizeof(a))
const int maxn=100005;
int n,m;
int vis[maxn];
int deep[maxn];
int dis[maxn];
int p[maxn][25];
vector<int>v1[maxn];
int tot;
struct node
{
    int u,v,w,nex;
} e[maxn*10];
int first[maxn];

void edge(int u,int v,int w)
{
    e[tot].v=v;
    e[tot].w=w;
    e[tot].nex=first[u];
    first[u]=tot++;
}
void init()
{
    tot=0;
    mem(first,-1);
    mem(vis,0);
    mem(dis,0);
    mem(deep,0);
    mem(p,0);
    for(int i=0; i<=n; i++)
        v1[i].clear();
}
void dfs(int u,int d,int pre)
{
    vis[u]=1;
    dis[u]=d;
    for(int i=1; i<=22; i++)
    {
        p[u][i]=p[p[u][i-1]][i-1];
    }
    for(int i=first[u]; i!=-1; i=e[i].nex)
    {
        int v=e[i].v;
        if(pre==v) continue;
        if(!vis[v])
        {
            deep[v]=deep[u]+1;
            p[v][0]=u;
            dfs(v,d+e[i].w,u);
        }
    }
}
int LCA(int x,int y)
{
    if(deep[x]<deep[y]) swap(x,y);
    for(int i=22; i>=0; i--)
    {
        if(deep[y]<=deep[p[x][i]])
        {
            x=p[x][i];
        }
    }
    if(x==y) return x;
    for(int i=22; i>=0; i--)
    {
        if(p[x][i]!=p[y][i])
        {
            x=p[x][i];
            y=p[y][i];
        }
    }
    return p[x][0];
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        init();
        int u,v,w;
        for(int i=1; i<n; i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            edge(u,v,w);
            edge(v,u,w);
        }
        for(int i=1; i<=m; i++)
        {
            int p;
            scanf("%d",&p);
            for(int j=1; j<=p; j++)
            {
                int aa;
                scanf("%d",&aa);
                v1[i].push_back(aa);
            }
        }
        dfs(1,0,-1);
        int q;
        scanf("%d",&q);
        for(int i=1; i<=q; i++)
        {
            int minn=inf;
            scanf("%d%d",&u,&v);
            for(int j=0; j<v1[u].size(); j++)
            {
                for(int k=0; k<v1[v].size(); k++)
                {
                    int uu=v1[u][j];
                    int vv=v1[v][k];
                    int gg=LCA(uu,vv);
                    //printf("gg=%d\n",gg);
                    minn=min(minn,dis[uu]+dis[vv]-2*dis[gg]);
                }
            }
            printf("%d\n",minn);
        }
    }
    return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注