Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- int n, q;
- int x[3];
- int a[400000];
- int d[400000];
- int p[400000];
- pair<int, int> tree[400000];
- vector<int> g[400000];
- vector<int> v;
- pair<int, int> mp(pair<int, int> lhs, pair<int, int> rhs)
- {
- if (lhs.first < rhs.first)
- return lhs;
- return rhs;
- }
- void dfs(int curr, int prev, int dpt)
- {
- v.push_back(dpt);
- a[curr] = v.size() - 1;
- d[curr] = dpt;
- p[v.size() - 1] = curr;
- for (int i = 0; i < g[curr].size(); i++)
- {
- if (g[curr][i] == prev) continue;
- dfs(g[curr][i], curr, dpt + 1);
- v.push_back(dpt);
- a[curr] = v.size() - 1;
- d[curr] = dpt;
- p[v.size() - 1] = curr;
- }
- }
- void build(int node, int s, int e)
- {
- if (s > e)
- return;
- if (s == e)
- {
- tree[node] = make_pair(v[s], s);
- return;
- }
- int mid = (s + e) / 2;
- build(2 * node, s, mid);
- build(2 * node + 1, mid + 1, e);
- tree[node] = mp(tree[2 * node], tree[2 * node + 1]);
- }
- pair<int, int> query(int node, int s, int e, int l, int r)
- {
- if (s > r || l > e || s > e)
- return make_pair(1 << 30, l);
- // cout << s << " " << e << " " << l << " " << r << endl;
- if (s >= l && e <= r)
- return tree[node];
- int mid = (s + e) / 2;
- pair<int, int> s1 = query(2 * node, s, mid, l, r);
- pair<int, int> s2 = query(2 * node + 1, mid + 1, e, l, r);
- // cout << s << " " << e << " " << l << " " << r << ": " << s1.first << " " << s1.second << "; " << s2.first << " " << s2.second << endl;
- return mp(s1, s2);
- }
- int dst(int ca, int cb)
- {
- int can = p[query(1, 0, n - 1, min(a[ca], a[cb]), max(a[ca], a[cb])).second];
- cout << ca + 1 << " -> " << cb + 1 << " " << can + 1 << ": " << d[ca] << " - " << d[can] << " + " << d[cb] << " = " << d[ca] - d[can] + d[cb] << endl;
- return d[ca] - d[can] + d[cb];
- }
- int main()
- {
- ifstream cin("in.txt");
- cin >> n >> q;
- int curr;
- for (int i = 1; i < n; i++)
- {
- cin >> curr;
- g[i].push_back(curr - 1);
- g[curr - 1].push_back(i);
- }
- dfs(0, -1, 0);
- build(1, 0, v.size() - 1);
- // for (int i = 0; i < v.size(); i++)
- // cout << p[i] + 1 << " ";
- // cout << endl;
- // for (int i = 0; i < v.size(); i++)
- // cout << v[i] << " ";
- // cout << "\n\n";
- int ac, bc, ab, cres, res;
- for (int i = 0; i < q; i++)
- {
- for (int j = 0; j < 3; j++)
- {
- cin >> x[j];
- x[j]--;
- }
- // sort(x, x + 3);
- res = 0;
- // do
- // {
- ac = p[query(1, 0, v.size() - 1, min(a[x[0]], a[x[2]]), max(a[x[0]], a[x[2]])).second];
- bc = p[query(1, 0, v.size() - 1, min(a[x[1]], a[x[2]]), max(a[x[1]], a[x[2]])).second];
- ab = p[query(1, 0, v.size() - 1, min(a[x[0]], a[x[1]]), max(a[x[0]], a[x[1]])).second];
- cout << ac + 1 << " " << bc + 1 << " " << ab + 1 << endl;
- cres = 0;
- if (ac == bc)
- cres += dst(ab, ac);
- cres += dst((d[ac] > d[bc] ? ac : bc), x[2]);
- res = max(cres, res);
- // }
- // while (next_permutation(x, x + 3));
- cout << res + 1 << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement