题目描述

欢乐岛上有个非常好玩的游戏，叫做“紧急集合”。在岛上分散有N个等待点，有N-1条道路连接着它们，每一条道路都连接某两个等待点，且通过这些道路可以走遍所有的等待点，通过道路从一个点到另一个点要花费一个游戏币。

参加游戏的人三人一组，开始的时候，所有人员均任意分散在各个等待点上（每个点同时允许多个人等待），每个人均带有足够多的游戏币（用于支付使用道路的花费）、地图（标明等待点之间道路连接的情况）以及对话机（用于和同组的成员联系）。当集合号吹响后，每组成员之间迅速联系，了解到自己组所有成员所在的等待点后，迅速在N个等待点中确定一个集结点，组内所有成员将在该集合点集合，集合所用花费最少的组将是游戏的赢家。

小可可和他的朋友邀请你一起参加这个游戏，由你来选择集合点，聪明的你能够完成这个任务，帮助小可可赢得游戏吗？

输入输出格式

输入格式：

第一行两个正整数N和M（N<=500000，M<=500000），之间用一个空格隔开。分别表示等待点的个数（等待点也从1到N进行编号）和获奖所需要完成集合的次数。随后有N-1行，每行用两个正整数A和B，之间用一个空格隔开，表示编号为A和编号为B的等待点之间有一条路。接着还有M行，每行用三个正整数表示某次集合前小可可、小可可的朋友以及你所在等待点的编号。

输出格式：

一共有M行，每行两个数P,C，用一个空格隔开。其中第i行表示第i次集合点选择在编号为P的等待点，集合总共的花费是C个游戏币。

输入输出样例

输入样例#1：

输出样例#1：

5 2

2 5

4 1

6 0

这个就用到了我们的LCA求解了，先用了Tarjan，然后被卡了（不能用O2）（之后再分析为什么会卡），用了倍增才过，根据题目，我们可以很容易地想到用lca来解决这个树上两点之间距离。树的剖分应该是正解吧（可惜我刚学，不太熟练 QAQ ）；

我们先看一下题目，是三个点到一个点的距离之和最小，图大家可以手模一下，我们设题中给的三个点为x,y,z,每两个点的lca是a,b,c. 距离前缀和数组设为dep[i];那么开始推导：肯定有lca是相同的，这个可以手动证明一下，这里就不再证明了，所以暂设 a==c=true ,那么， _dep[x]+dep[y]-2dep[a]+dep[z]-dep[b]+dep[a]-dep[b]==_dep[x]+dep[y]+dep[z]-2dep[a]-dep[b] ，然后大家应该就能懂了QAQ，之后还有通用公式 dep[x]+dep[y]+dep[z]-dep[a]-dep[b]-dep[c] ,只要再找到a,b,c中谁与其它两个不同即可；

然后附上Code

Code

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

using namespace std;

int n,m,head[],cent,dep[],fa[][],len[];

struct node{

    int next,to,w;

}edge[];

void add(int u,int v,int w){

    edge[++cent]=(node){head[u],v,w};head[u]=cent;

}

void dfs(int x,int dy){

    dep[x]=dy;//求深度

    for(int i=head[x];i;i=edge[i].next){

        int y=edge[i].to;

        if(y==fa[x][]) continue;

        fa[y][]=x;

        len[y]=len[x]+edge[i].w;//其实与深度一样

        dfs(y,dy+);

    }

    return ;

}

void Init(){

    fa[][]=-;

    dfs(,);

    for(int i=;<<i<n;i++){//倍增

        for(int j=;j<=n;j++){//更新每一个点

            if(fa[j][i-]<) fa[j][i]=-;

            else fa[j][i]=fa[fa[j][i-]][i-];

        }

    }

    return ;

}

int lca(int x,int y){

    if(dep[x]<dep[y]) swap(x,y);

    for(int i=,d=dep[x]-dep[y];d;d>>=,i++){

        if(d&) x=fa[x][i];//转移至同一高度

    }

    if(x==y) return x;

    for(int i=log(n)+;i>=;i--){//寻找LCA

        if(fa[x][i]!=fa[y][i]){//自己画图体会一下

            x=fa[x][i];

            y=fa[y][i];

        }

    }

    return fa[x][];

}

void work(int a,int b,int c){

    int x=lca(a,b),y=lca(b,c),z=lca(a,c),exit;

    if(x==y) exit=z;

    else if(y==z) exit=x;

    else if(x==z) exit=y;//寻找不同的LCA

    printf("%d %d\n",exit,dep[a]+dep[b]+dep[c]-dep[x]-dep[y]-dep[z]);//通用公式计算

}

int main(){

    scanf("%d%d",&n,&m);

    for(int i=,a,b;i<=n-;i++){

        scanf("%d%d",&a,&b);

        add(a,b,),add(b,a,);//存图

    }

    Init();//初始化

    for(int i=,a,b,c;i<=m;i++){

        scanf("%d%d%d",&a,&b,&c);

        work(a,b,c);

    }

    return ;

}

至于为什么Tarjan没过而倍增过了，是因为我们统计倍增O（nlongn+mlongn），而实际上，大部分数据查询是不需要logn的，所以就将倍增算法捧上了天，而作为O（n+m）算法的Tarjan却栽了是因为并查集维护时，时间复杂度最坏达到了近O（n2+m），但是O(1)查询的Tarjan在一些数据确实比倍增算法快，但是，在一些非常诡异的数据中，还是用倍增比较妥当，来看代码

Code

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

using namespace std;

int n,m,head[],cent,cnt,h[],dep[],vis[];

int fa[],f[],see[][],num[];

struct node{

    int next,to,w;

}edge[];

struct node1{

    int next,to,id;

}e[];

template<typename type_of_scan>

inline void scan(type_of_scan &x){

    type_of_scan f=;x=;char s=getchar();

    while(s<''||s>''){if(s=='-')f=-;s=getchar();}

    while(s>=''&&s<=''){x=x*+s-'';s=getchar();}

    x*=f;

}

inline void add(int u,int v,int w){

    edge[++cent]=(node){head[u],v,w};head[u]=cent;

}

inline void add1(int u,int v,int name){

    e[++cnt]=(node1){h[u],v,name};h[u]=cnt;

}

inline int get(int x){

    if(fa[x]==x) return x;

    return fa[x]=get(fa[x]);

}

inline void Tarjan(int u){

    vis[u]=;

    for(register int i=head[u];i;i=edge[i].next){

        int v=edge[i].to;

        if(vis[v]) continue;

        dep[v]=dep[u]+edge[i].w;//与倍增一样

        Tarjan(v);

        fa[v]=u;

    }

    for(register int i=h[u];i;i=e[i].next){

        int v=e[i].to;

        if(vis[v]&&!f[e[i].id]){

            int zz=get(v),x=e[i].id;

            f[x]=zz;//储存答案

        }

    }//与倍增不同的是，它每次都去处理有关点数据，运用访问时间的差别，以来实现Tarjan

}

inline void work(){

    for(register int i=;i<=*m;i+=){

        int x=see[i][],y=see[i][],z=see[i][];

        int a=f[i],b=f[i+],c=f[i+];

        if(a==b){

            printf("%d %d\n",c,dep[x]+dep[y]+dep[z]-dep[a]-dep[b]-dep[c]);

        }else if(b==c) {

            printf("%d %d\n",a,dep[x]+dep[y]+dep[z]-dep[a]-dep[b]-dep[c]);

        }else if(a==c) {

            printf("%d %d\n",b,dep[x]+dep[y]+dep[z]-dep[a]-dep[b]-dep[c]);

        }

    }

}

int main(){

    scan(n),scan(m);

    for(int i=;i<=n;i++) fa[i]=i;

    for(int i=,a,b;i<=n-;i++){

        scan(a),scan(b);

        add(a,b,),add(b,a,);

    }

    for(register int i=;i<=*m;i+=){

        int a,b,c;

        scan(a),scan(b),scan(c);//Tarjan储存询问，在工作时一起解决

        see[i][]=a,see[i][]=b,see[i][]=c;

        add1(a,b,i),add1(b,a,i),add1(a,c,i+);

        add1(c,a,i+),add1(c,b,i+),add1(b,c,i+);

    }

    Tarjan();

    work();

    return ;

}

先说到这里

巴特西

图论分支-倍增Tarjan求LCA

题目描述

输入输出格式

输入输出样例

Code

最新文章

热门文章