Last active
May 12, 2021 14:08
-
-
Save overnew/4d795c625b0677160b9e8f9316b380c6 to your computer and use it in GitHub Desktop.
[AlgoSpot]_FAMILYTREE_족보 탐험
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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