xiaoMa
"Bye Bye Baby Blue"
LCA树上倍增(HDU-2586)
 勇气小镇是一个有着n个房屋的小镇,为什么把它叫做勇气小镇呢,这个故事就要从勇气小镇成立的那天说起了,
修建小镇的时候,为了让小镇有特色,镇长特地只修了n-1条路,并且规定说,所有在勇气小镇的村民,每一次出门必须规划好路线
,路线必须满足在到达终点之前绝对不走回头路。每个人都要这样,不然那个人就不配在小镇生活下去,因为他没有这个勇气。
事实上,这并不能算一项挑战,因为n-1条路已经连通了每户人家,不回头地从起点到终点,只是一个时间上的问题。
由于小镇上的福利特别好,所以小懒入住了这个小镇,他规划了m次的行程,每次从L房屋到R房屋,他想问你他每次从L房屋到R房屋
需要走多远的路。 

Input

 输入的第一行是一个整数t,表示有t组数据
  每组数据第一行是n,m两个数字,分别表示小镇上房屋的个数,和小懒计划的行程的数量。
之后第2行到第n行,每行三个整数a,b,c表示,a房屋与b房屋之间连接着一条距离为c的小路。
第n+1行到第n+m行,每行两个整数,L,R,代表一次小懒的询问,也就是询问小懒从L房屋走到R房屋所走的最近距离为多少。

一道比较裸的LCA,主要意思就是给一颗无根树,有n次查询,查询两个点之间的距离。

一种朴素的算法是,两个结点同时往上跳,知道跳到LCA为止,这种算法的复杂度是 O(n*m),肯定是TLE了,而倍增LCA的复杂度为约为O((n+m)log n)

BFS维护每个节点的i的向上 2^j个节点f[i][j],由于存在 1,2,4,8,…,2^n等数能组成1-2^n所有数的性质,这样在向上寻找询问点的祖先时能得到一个logn级别的优化 。

详细注释在下方。有个半年没写了…写得有点晕,tarjan那种离线的做法不会了?

如果不懂倍增什么意思的话,可以先去看看ST表?

/**
 * KUANGBIN___HDU_2586_2_CPP
 * @author : MaWeiTao
 * @date : 20:25 2020/2/29
 *
 */

#include<bits/stdc++.h>
using namespace std;

const int maxn=2e5+6;
const int N=50010;
struct Edge{
    int to,w,next;
}e[maxn<<1];    //链式前向星
int head[N],cnt=0;
int vis[N];  //visit
int dis[N],fa[N][30],deg[N];
//dis表示到根节点的距离 fa[i][j]表示i的ST表,记录n的祖先节点,deg[n]表示到根节点深度

int T;

void add(int x,int y,int z)//链式前向星--加边
{
    e[cnt].to=y,e[cnt].w=z,e[cnt].next=head[x];
    head[x]=cnt++;
}

void bfs(int be)
{
    queue<int> q;
    memset(vis,0,sizeof(vis));
    memset(fa,0,sizeof(fa));
    q.push(be);
    vis[be]=1;//标记该点已经访问
    deg[be]=1;//默认根节点深度为1,注意根节点深度不能为0
    while(q.size())         //常规的bfs
    {
        int x=q.front();
        q.pop();
        for(int i=head[x];~i;i=e[i].next)//遍历节点x的邻接点
        {
            int y=e[i].to;
            if(!vis[y])
            {
                dis[y]=dis[x]+e[i].w;//和根节点的长度
                deg[y]=deg[x]+1;//深度
                vis[y]=1;//标记该点
                fa[y][0]=x;//存父节点
                for(int j=1;j<=T;j++){
                    fa[y][j]=fa[fa[y][j-1]][j-1];//存储第f(y,j<<1)个祖先节点
                }
                q.push(y);
                //将该节点入队,如果邻接点遍历完,取队顶的最先入队的邻接点开始遍历他的邻接点
            }
        }
    }
}

int LCA(int x,int y)
{
    if(deg[x]>deg[y])	swap(x,y);//保持 y>=x
    for(int i=T;i>=0;i--)//让y上升到与x同一深度
        if(deg[fa[y][i]]>=deg[x])	y=fa[y][i];
    if(x==y)	return x;//如果此时相等,那就返回
    for(int i=T;i>=0;i--)//让x和y同时上升 同一段距离
        if(fa[x][i]!=fa[y][i])	x=fa[x][i],y=fa[y][i];
    return fa[x][0];//返回父节点。
}

int main()
{
    std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
    //用不用取消流同步差距很大,170ms->30ms
    int t,n,m;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        T=int(log(n)/log(2))+1;
        //这里也可以常数优化,先离线算出lg[n]
        /*
         * for(int i=1;i<=n;i++)lg[i]=lg[i-1]+(lg[i-1]<<1==i);
         */
        memset(head,-1,sizeof(head));//链式前向星head数组初始化-1
        cnt=0;
        for(int i=0;i<n-1;i++)//存边
        {
            int x,y,z;
            cin>>x>>y>>z;
            add(x,y,z);
            add(y,x,z);
        }
        bfs(1);
        while(m--)//q次询问
        {
            int x,y;
            cin>>x>>y;
            cout<<(dis[x]+dis[y]-2*dis[LCA(x,y)])<<endl;
        }
    }
    return 0;
}

发表评论

textsms
account_circle
email

LCA树上倍增(HDU-2586)
勇气小镇是一个有着n个房屋的小镇,为什么把它叫做勇气小镇呢,这个故事就要从勇气小镇成立的那天说起了, 修建小镇的时候,为了让小镇有特色,镇长特地只修了n-1条路,并且规定说,所有…
扫描二维码继续阅读
2020-02-29