题目地址：HDU 2874 好坑的一道题。。MLE了好长时间、。、。全用了前向星而且把G++改成了C++才过了。。 LCA裸题，没什么好说的。。 代码如下;
;mod=1e9+7;const int INF=0x3f3f3f3f;const double eqs=1e-9;const int MAXN=200000+10;int head[10001], head1[10001], cnt, cnt1, lca[1000001], bin[10001], d[10001], ffa[10001], n;struct node{int v, w, next;}edge[20001];struct N{int v, id, next;}edge1[2000001];void add(int u, int v, int w){edge[cnt].v=v;edge[cnt].w=w;edge[cnt].next=head[u];head[u]=cnt++;}void add1(int u, int v, int id){edge1[cnt1].v=v;edge1[cnt1].id=id;edge1[cnt1].next=head1[u];head1[u]=cnt1++;}bool vis[10001];int find1(int x){return bin[x]==x?x:bin[x]=find1(bin[x]);}void tarjan(int u, int root){vis[u]=1;ffa[u]=root;int i;for(i=head1[u];i!=-1;i=edge1[i].next){int v=edge1[i].v;if(!vis[v]||ffa[u]!=ffa[v]) continue ;lca[edge1[i].id]=d[u]+d[v]-2*d[find1(bin[v])];}for(i=head[u];i!=-1;i=edge[i].next){int v=edge[i].v;if(vis[v]) continue ;d[v]=d[u]+edge[i].w;tarjan(v,root);bin[v]=u;}}void init(){memset(head,-1,sizeof(head));memset(head1,-1,sizeof(head1));cnt=cnt1=0;memset(lca,-1,sizeof(lca));memset(vis,0,sizeof(vis));for(int i=1; i<=n; i++) {bin[i]=i;}}int main(){int m, qu, i, j, u, v, w;while(scanf(“%d%d%d”,&n,&m,&qu)!=EOF) {init();while(m–) {scanf(“%d%d%d”,&u,&v,&w);add(u,v,w);add(v,u,w);}for(i=0; i<qu; i++) {scanf(“%d%d”,&u,&v);add1(u,v,i);add1(v,u,i);}for(i=1; i<=n; i++) {if(!vis[i]) {d[i]=0;tarjan(i,i);}}for(i=0; i<qu; i++) {if(lca[i]==-1) puts(“Not connected”);else printf(“%d\n”,lca[i]);}}return 0;}
，只有不快的斧，没有劈不开的柴。
