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;
}

补充：软件开发 , C++ ,