求任意兩點到最近公共祖先的距離

　　虛擬賽的時候一看是求任意兩點的最短路不管怎麼優化都超時最近做一些樹的題目這是求任意兩點到最近公共祖先的距離先用並差集判斷是否聯通聯通就求最近公共祖先先把圖建成一棵棵樹
    #include<stringh>
    #include<stdioh>
    #define N
    int father[N]dfs[N]nvis[N]head[N]numf[N]ansdis[N];
    struct edge
    {
    int stednextw;
    }E[N*];
    void addedge（int xint yint w）
    {
    E[num]st=x;
    E[num]ed=y;
    E[num]w=w;
    E[num]next=head[x];
    head[x]=num++;
    }
    int find（int a）
    {
    if（f[a]!=a）
    f[a]=find（f[a]）
    return f[a];
    }
    void dfs（int u）
    {
    int iv;
    vis[u]=;
    for（i=head[u];i!=;i=E[i]next）
    {
    v=E[i]ed;
    if（vis[v]==）continue;
    father[v]=u;
    dfs[v]=dfs[u]+;
    dis[v]=E[i]w;
    dfs（v）
    }
    if（ans<dfs[u]）
    ans=dfs[u];
    }
    int LCA（int xint y）
    {
    int sum=;
    while（dfs[x]>dfs[y]）
    {
    sum+=dis[x];
    x=father[x];
    }

　　while（dfs[y]>dfs[x]）
    {
    sum+=dis[y];
    y=father[y];
    }
    while（x!=y）
    {
    sum+=（dis[x]+dis[y]）
    x=father[x];
    y=father[y];
    }
    return sum;
    }
    int main（）
    {
    int ijkxymansw;
    while（scanf（%d%d%d&n&m&k）！=）
    {
    memset（headsizeof（head））
    num=;
    for（i=;i<=n;i++）
    f[i]=i;
    for（i=;i<m;i++）
    {
    scanf（%d%d%d&x&y&w）
    addedge（xyw）
    addedge（yxw）
    x=find（x）
    y=find（y）
    if（x!=y）
    f[x]=find（y）
    }
    memset（vissizeof（vis））
    ans=;
    for（i=;i<=n;i++）
    {
    if（vis[i]==）
    {
    dis[i]=;
    dfs[i]=ans;
    father[i]=i;
    dfs（i）
    ans++;
    }
    }
    while（k）
    {
    scanf（%d%d&x&y）
    if（find（x）！=find（y））
    {printf（Not connected\n）continue;}
    j=LCA（xy）
    printf（%d\nj）
    }
    }
    return ;
    }

From:http://tw.wingwit.com/Article/program/c/201311/11104.html