1. 首页
2. LCA
3. 本页

HDU 2586 How far away ？(LCA离线算法)

传送门：点我~~

题意：有n个房子，用n-1条边连接起来，接下了有m次询问，询问两个房子之间的距离是多少。先建一棵树，然后求出每一点i到树根的距离dis[i],然后每次询问a，b之间的距离=dis[a]+dis[b]-2*dis[LCA(a,b)]，LCA(a,b)即是a，b的最近公共祖先。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int mod = 1e9;
const int M = 1000000+10;

const int MAXN = 201010;
const int MAXQ = 30000;

int F[MAXN];
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,val;
} edge[MAXN*2];
int head[MAXN*2],tot;
int dis[MAXN*2];


void addedge(int u,int v,int w)
{
    edge[tot].to = v;
    edge[tot].val = w;
    edge[tot].next = head[u];
    head[u] = tot++;
}

struct Query
{
    int q,next;
    int to;
    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].to = u;
    query[tt].index = index;
    h[u] = tt++;
    query[tt].q = u;
    query[tt].next = h[v];
    query[tt].to = 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));
    dis[1]=0;
}

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;
        dis[v]=dis[u]+edge[i].val;
        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()
{
    int n;
    int u,v,k;
    int w;
    int t,Q;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&Q);
        init();
        memset(flag,false,sizeof(flag));
        for(int i = 1; i < n; i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            flag[v] = true;
            addedge(u,v,w);
            addedge(v,u,w);
        }
        for(int i = 1; i <= Q; i++)
        {
            scanf("%d%d",&u,&v);
            add_query(u,v,i);
        }
        int root;
        for(int i = 1; i <= n; i++)
            if(!flag[i])
            {
                root = i;
                break;
            }
        LCA(root);
        for(int i = 1; i < tt; i+=2) //query 1=2 就是查询询问插入的a b的祖先
        {
            cout<<answer[query[i].index]<<endl;
            printf("%d\n",dis[query[i].q]+dis[query[i].to]-2*dis[answer[query[i].index]]);
        }
    }
    return 0;
}