Design the city-LCA/SparseTable

update@2011-08-22

struct tree_node    {int v,d;};
vector<tree_node>   tree[50000];
struct query_node   {int v,i_one,i_two;};
vector<query_node>  query_set[50000];

int is_root[50000],father[50000],visited[50000],dist[50000],ans[70000][3];

int FindSet(int x){
    return x == father[x]?x:(father[x] = FindSet(father[x]));
}
void UnionSet(int x,int y){
    father[FindSet(y)] = FindSet(x);
}
void Tarjan_LCA(int u){
    int size_tree = tree[u].size();
    for(int i = 0;i < size_tree;i++){//遍历该节点的每个子节点
        Tarjan_LCA(tree[u][i].v);
        UnionSet(u,tree[u][i].v);
    }
    visited[u] = true;//访问是有序的但a b是无序的所以要进行标记
    int size_query_set = query_set[u].size();
    for(int i = 0;i < size_query_set;i++){
        if(visited[query_set[u][i].v]){
            ans[query_set[u][i].i_one][query_set[u][i].i_two] =\
             dist[u] + dist[query_set[u][i].v] -\
            2*dist[FindSet(query_set[u][i].v)];
            //u到v的距离等于u到根的距离加上v到根的距离减去2倍LCA(u,v)到根的距离
        }
    }
}
void init(int n){
    for(int i = 0;i < n;i++){
        tree[i].clear();
        query_set[i].clear();//query_set[i][j] (i < n)
        father[i] = i;visited[i] = false;is_root[i] = true;
    }
}
int findRoot(int n){
    for(int i = 0;i < n;i++){
        if(is_root[i] == 1)return i;
    }
    return -1;
}
void dist_DFS(int u,int di)
{
    //深搜计算每个点到根的距离
    int size_tree = tree[u].size();
    for(int i = 0;i < size_tree;i++){
        dist[tree[u][i].v] = di + tree[u][i].d;
        dist_DFS(tree[u][i].v,dist[tree[u][i].v]);
        //tree[u][i].d 为 u到tree[u][i].v的距离
    }
}

//main函数中的主要部分
init(n);
for(i = 1;i < n;i++){
    scanf("%d%d%d",&a,&b,&d);
    tree_node temp;temp.d = d;
    if(is_root[b] == false){
        //每个节点可以多次作为父节点但只能作一次子节点
        //即入度为1(根节点入度为0 也是根据这个来确定根节点的)
        //这个就是构造树的过程
        is_root[a] = false;temp.v = a;
        tree[b].push_back(temp);
    }
    else{
        is_root[b] = false;temp.v = b;
        tree[a].push_back(temp);
    }
}
int Q;scanf("%d",&Q);
for(int i = 0;i < Q;i++){
    scanf("%d%d%d",&a,&b,&c);
    query_node temp;temp.i_one = i;
    temp.v = b; temp.i_two = 0;
    query_set[a].push_back(temp);//a b
    temp.v = a;
    query_set[b].push_back(temp);//a b
    temp.v = c; temp.i_two = 1;
    query_set[a].push_back(temp);//a c
    temp.v = a;
    query_set[c].push_back(temp);//a c
    temp.v = c; temp.i_two = 2;
    query_set[b].push_back(temp);//b c
    temp.v = b;
    query_set[c].push_back(temp);//b c

}
root = findRoot(n); dist[root] = 0; dist_DFS(root,0);
Tarjan_LCA(root);if(test++printf("\n");
for(int i = 0;i < Q;i++){
    //减去重复的路径就是题目要求的结果
    printf("%d\n",(ans[i][0] + ans[i][1] + ans[i][2])/2);
}




题目链接:Design the city
这题不难,开始的时候没有想到是用LCA解(一直纳闷sample中的结果 我以为直接是距离加一下就行),然后想到的是floyd,floyd复杂度太高不可能行的,然后看了解题报告才知道要用LCA。先搞懂LCA 刷一个基础的LCA题,再来A这个就很简单了,不过感觉自己写的很二,可以看看fookwood的ST (ST看过,忘的差不多了,好像要注意的是初始化的时的一个dp)。