10
15
2015
0

[BZOJ1602] [Usaco2008 Oct] 牧场行走

这是一个很裸的LCA。

觉得hzwer的LCA模版更加优美,于是膜拜了一下。

#include<cstdio>
#include<algorithm>
using namespace std;

int fa[1005][12],f[1005],n,q,en,h[1005],deep[1005],flg[1005];

struct Edge{
int b,v,next;
}e[2005];

void add(int sa,int sb,int sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}

void Yuchuli(int u){
flg[u]=1;
for(int i=1;i<=10;i++){
    if(deep[u]<(1<<i))break;
    fa[u][i]=fa[fa[u][i-1]][i-1];
}
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(flg[v])continue;
    f[v]=f[u]+e[i].v;
    fa[v][0]=u;
    deep[v]=deep[u]+1;
    Yuchuli(v);
}
}

int LCA(int u,int v){
if(deep[u]<deep[v])swap(u,v);
int dep=deep[u]-deep[v];
for(int i=0;i<=10;i++)if((1<<i)&dep)u=fa[u][i];
for(int i=10;i>=0;i--){
    if(fa[u][i]!=fa[v][i]){
        u=fa[u][i];
        v=fa[v][i];
    }
}
return u==v?u:fa[u][0];
}

int main(){
freopen("1602.in","r",stdin);
freopen("1602.out","w",stdout);
scanf("%d %d",&n,&q);
for(int i=1;i<n;i++){
    int sa,sb,sc;
    scanf("%d %d %d",&sa,&sb,&sc);
    add(sa,sb,sc);
    add(sb,sa,sc);
}
Yuchuli(1);
while(q--){
    int sa,sb;
    scanf("%d %d",&sa,&sb);
    printf("%d\n",f[sa]+f[sb]-2*f[LCA(sa,sb)]);
}
return 0;
}
Category: BZOJ | Tags: bzoj | Read Count: 495

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com