hdu 2586 lca在线算法(朴素算法)

#include<stdio.h>

#include<string.h>//用c/c++会爆栈，用g++ac

#define inf 0x3fffffff

#define N 41000

struct node {

int u,v,w,next;

}bian[N*2];

int head[N],yong;

int pre[N],dis[N],deep[N];

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

bian[yong].u=u;

bian[yong].v=v;

bian[yong].w=w;

bian[yong].next=head[u];

head[u]=yong++;

}

void dfs(int s,int h,int pr){

int i;

deep[s]=h+1;

for(i=head[s];i!=-1;i=bian[i].next) {

if(bian[i].v!=pr) {

pre[bian[i].v]=s;

dis[bian[i].v]=dis[s]+bian[i].w;

dfs(bian[i].v,h+1,s);

}

}

return ;

}

int lca(int u,int v) {

if(u==v)

return u;

if(deep[u]>deep[v])

return lca(pre[u],v);

return lca(u,pre[v]);

}

int main() {

int n,m,i,u,v,w,t;

scanf("%d",&t);

while(t--) {

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

memset(head,-1,sizeof(head));

yong=0;

for(i=1;i<n;i++) {

scanf("%d%d%d",&u,&v,&w);

addedge(u,v,w);

addedge(v,u,w);

}

dis[1]=0;

dfs(1,-1,1);

while(m--) {

scanf("%d%d",&u,&v);

w=lca(u,v);

printf("%d\n",dis[u]+dis[v]-2*dis[w]);

}

}

return 0;

}

巴特西

hdu 2586 lca在线算法(朴素算法)

最新文章

热门文章