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)。