Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <vector>
- using namespace std;
- const int N = 100010;
- const int M = 2000010;
- ifstream F("lca.in");
- ofstream G("lca.out");
- int n, m, dad[N], ancestor[N], lvl[N];
- bool black[N];
- int ans[M];
- vector<int> v[N];
- #define y first
- #define ord second
- vector<pair<int, int> > w[N];
- int find(int x) {
- if (dad[x] != x) {
- dad[x] = find(dad[x]);
- }
- return dad[x];
- }
- void union2(int x, int y) {
- x = find(x);
- y = find(y);
- if (lvl[x] > lvl[y]) {
- dad[y] = x;
- } else {
- dad[x] = y;
- if (lvl[x] == lvl[y]) {
- lvl[x]++;
- }
- }
- }
- void lca(int x) {
- dad[x] = x;
- lvl[x] = 0;
- ancestor[x] = x;
- for (int y : v[x]) {
- lca(y);
- union2(x, y);
- ancestor[find(x)] = x;
- }
- black[x] = 1;
- for (pair<int, int> p : w[x]) {
- if (black[p.y]) {
- ans[p.ord] = ancestor[find(p.y)];
- }
- }
- }
- int main() {
- F >> n >> m;
- for (int y = 2, x; y <= n; ++y) {
- F >> x;
- v[x].push_back(y);
- }
- for (int i = 1, x, y; i <= m; ++i) {
- F >> x >> y;
- w[x].push_back(make_pair(y, i));
- w[y].push_back(make_pair(x, i));
- }
- lca(1);
- for (int i = 1; i <= m; ++i) {
- G << ans[i] << '\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement