Skip to content

Instantly share code, notes, and snippets.

@overnew
Last active May 12, 2021 14:08
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save overnew/4d795c625b0677160b9e8f9316b380c6 to your computer and use it in GitHub Desktop.
Save overnew/4d795c625b0677160b9e8f9316b380c6 to your computer and use it in GitHub Desktop.
[AlgoSpot]_FAMILYTREE_족보 탐험
#include<vector>
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
const int MAX_N = 100000;
vector<vector<int>> child;
int no2serial[MAX_N], serial2no[MAX_N];
int locInTrip[MAX_N], depth[MAX_N];
vector<int> trip;
vector<int> segment_tree;
int nextSerial;
int Init(int left, int right, int node){
if(left == right)
return segment_tree[node] = trip[left];
int mid = (left + right)/2;
return segment_tree[node] = min(Init(left, mid, node*2), Init(mid+1, right, node*2 +1));
}
int Query(int left, int right, int query_left, int query_right, int node){
if(right < query_left || query_right < left)
return INT32_MAX;
if(query_left<=left && right <= query_right)
return segment_tree[node];
int mid = (left + right)/2;
return min( Query(left, mid, query_left, query_right, node * 2), Query(mid+1, right, query_left, query_right, node * 2 + 1) );
}
void Traverse(int here, int d ){
no2serial[here] = nextSerial;
serial2no[nextSerial] = here;
++nextSerial;
depth[here] = d;
locInTrip[here] = trip.size();
trip.push_back(no2serial[here]);
for(int i=0; i<child[here].size() ; ++i){
Traverse(child[here][i] , d+1);
trip.push_back(no2serial[here]);
}
}
int main(){
int test_num,family_num,Q;
scanf("%d", &test_num);
while(test_num--){
scanf("%d %d", &family_num, &Q);
child.clear();
child = vector<vector<int>>(MAX_N);
int parent;
for(int i=1; i< family_num; ++i){
scanf("%d", &parent );
child[parent].push_back(i);
}
nextSerial=0;
Traverse(0 , 0);
int tree_hight = (int)ceil(log2(trip.size()));
segment_tree.clear();
segment_tree = vector<int>(1<<(tree_hight + 1));
Init(0, trip.size()-1, 1);
int a,b, lca, query_left, query_right;
while(Q--){
scanf("%d %d", &a, &b);
query_left = locInTrip[a];
query_right = locInTrip[b];
if(query_left > query_right)
swap(query_left,query_right);
lca = serial2no[ Query(0, trip.size()-1, query_left, query_right, 1)];
printf("%d\n", depth[a] + depth[b] - 2*depth[lca] );
}
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment