ural 1471 Tree題解

注意本題可能會Crash。采用Color[] = 0 1 2 的解法，而不用Parent[]限制一棵樹。

某種情況下也可以用

[cpp] 
#pragma comment(linker, "/STACK:1000000000") 
不過不推薦

代碼：

[cpp] 
#include <iostream> 
#include <stdlib.h> 
#include <stdio.h> 
#include <string.h> 
using namespace std; 
#define max 50010 
#define max2 75010 
int parent[max];//使沒向變為有向的標志 
int father[max];//並查集集合中的代表節點 
int ancestor[max];//LCA中的祖先節點 
int color[max];//深搜的標志 
int dis[max];//與根節點的距離 
int ran[max];//並查集森林中根節點的高度 
int quex[max2];//查詢的x 
int quey[max2];//查詢的y 
int final[max2];//兩節點的祖先 
struct edge 
{ 
    int y; 
    int w; 
    edge * next; 
    edge(int y1,int w1,edge * next1) 
    { 
        y = y1; 
            w = w1; 
        next = next1; 
    } 
}*E[max]; 
 
struct que 
{ 
    int y; 
    int n; 
    que * next; 
    que(int y1,int n1,que * next1) 
    { 
        y = y1; 
        n = n1; 
        next = next1; 
    } 
}*Q[max2]; 
void makeset(int i) 
{ 
    father[i] = i; 
    ran[i] = 1; 
} 
 
int findset(int i) 
{ 
    if(father[i] == i) 
    { 
        return i; 
    } 
    return father[i] = findset(father[i]); 
 
} 
 
int unionset(int x,int y) 
{ 
    int a = findset(x); 
    int b = findset(y); 
    if(a == b) 
    { 
        return 0; 
    } 
    else if(ran[a]>ran[b]) 
    { 
        father[b] = a; 
        ran[a]+=ran[b]; 
    } 
    else 
    { 
        father[a] = b; 
        ran[b] += ran[a]; 
    } 
    return 0; 
 
} 
 
void lca(int u) 
{ 
    color[u] = 1; 
    makeset(u); 
    ancestor[u] = u; 
    for(edge * e = E[u]; e ;e = e->next) 
    { 
        int v = e->y; 
        int wtemp = e->w; 
        if(color[v] ==0) 
        { 
            dis[v] = dis[u] + wtemp; 
 
            lca(v); 
            unionset(u,v); 
            ancestor[findset(u)] = u; 
        } 
    } 
    color[u] = 2; 
    for(que * q = Q[u];q;q=q->next) 
    { 
        int v = q->y; 
        if(color[v]==2) 
        { 
            final[q->n] = ancestor[findset(v)]; 
        } 
    } 
} 
int main() 
{ 
#ifndef ONLINE_JUDGE 
    freopen("in.txt","r",stdin); 
#endif 
    int n,m; 
    memset(E,0,sizeof(E)); 
    memset(Q,0,sizeof(Q)); 
    memset(final,0,sizeof(final)); 
    scanf("%d",&n); 
    for(int i=0;i<n-1;i++) 
    { 
        int a,b,c; 
        scanf("%d%d%d",&a,&b,&c); 
        E[a] = new edge(b,c,E[a]); 
        E[b] = new edge(a,c,E[b]); 
    } 
    parent[0] = -1;//lca從0開始 
    memset(dis,0,sizeof(dis)); 
    memset(color,0,sizeof(color)); 
    scanf("%d",&m); 
    for(int i=0;i<m;i++) 
    { 
        int x,y; 
        scanf("%d%d",&x,&y); 
        quex[i] = x; 
        quey[i] = y; 
        Q[x] = new que(y,i,Q[x]); 
        Q[y] = new que(x,i,Q[y]); 
    } 
    lca(0); 
    for(int i=0;i<m;i++) 
    { 
        printf("%d\n",dis[quex[i]] + dis[quey[i]] - 2 * dis[final[i]]); 
    } 
    return 0; 
}