首页 > 代码库 > BZOJ 1832 聚会

BZOJ 1832 聚会

不想写。。。直接粘过来。

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define N 501000#define LOGN 20#define inf 0x3f3f3f3fusing namespace std;struct KSD{    int v,next;}e[N<<1];int head[N],cnt;inline void add(int u,int v){    cnt++;    e[cnt].v=v;    e[cnt].next=head[u];    head[u]=cnt;}int n,m;int fa[N][LOGN],deep[N];void dfs(int x,int p){    int i,v;    deep[x]=deep[p]+1;    for(i=head[x];i;i=e[i].next)    {        v=e[i].v;        if(v==p)continue;        fa[v][0]=x;        dfs(v,x);    }    return ;}inline void array(){    int i,j;    for(j=1;j<LOGN;j++)        for(i=1;i<=n;i++)            fa[i][j]=fa[fa[i][j-1]][j-1];}int lcansx,lcansy;inline int getlca(int x,int y){    if(deep[x]<deep[y])swap(x,y);    int i,j,k;    lcansx=lcansy=0;    for(i=LOGN-1;i>=0;i--)        if(deep[fa[x][i]]>=deep[y])x=fa[x][i],lcansx+=(1<<i);    if(x==y)return x;    for(i=LOGN-1;i>=0;i--)        if(fa[x][i]!=fa[y][i])            x=fa[x][i],y=fa[y][i],lcansy+=(1<<i);    lcansy+=1,lcansx+=lcansy;    return fa[x][0];}int main(){//    freopen("test.in","r",stdin);    int i,ans,id;    int a,b,c;    scanf("%d%d",&n,&m);    for(i=1;i<n;i++)    {        scanf("%d%d",&a,&b);        add(a,b),add(b,a);    }    dfs(1,0);    array();    while(m--)    {        scanf("%d%d%d",&a,&b,&c);        int lca=getlca(a,b),temp=lcansx+lcansy;        getlca(lca,c);        temp+=lcansx+lcansy;        ans=temp,id=lca;        lca=getlca(a,c),temp=lcansx+lcansy;        getlca(lca,b);        temp+=lcansx+lcansy;        if(ans>temp)ans=temp,id=lca;        lca=getlca(b,c),temp=lcansx+lcansy;        getlca(lca,a);        temp+=lcansx+lcansy;        if(ans>temp)ans=temp,id=lca;        printf("%d %d\n",id,ans);    }    return 0;}

 

BZOJ 1832 聚会