1. 首页
  2. LCA

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;
}

 

评分 0, 满分 5 星
0
0
看完收藏一下,下次也能找得到
  • 版权声明:本文基于《知识共享署名-相同方式共享 3.0 中国大陆许可协议》发布,转载请遵循本协议
  • 文章链接:http://www.carlstedt.cn/archives/1020 (转载时请注明本文出处及文章链接)
上一篇:
:下一篇

发表评论

gravatar

快来吐槽一下吧!

  1. .01 4:06
  2. .02 1:47
  3. .03 3:39
  4. .04 1:40