Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //misaka and rin will carry me to cm
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- #include <utility>
- #include <cassert>
- #include <algorithm>
- #include <vector>
- #include <array>
- #include <tuple>
- #define ll long long
- #define lb long double
- #define sz(vec) ((int)(vec.size()))
- #define all(x) x.begin(), x.end()
- #define LC(x) ((x)*2 +1)
- #define RC(x) ((x)*2 +2)
- const lb eps = 1e-9;
- const ll mod = 1e9 + 7, ll_max = 1e18;
- //const ll mod = (1 << (23)) * 119 +1;
- const int MX = 4e5 +10, int_max = 0x3f3f3f3f;
- using namespace std;
- //i will learn from moo.
- /* Input */
- template<class T> void read(T &x) { cin >> x; }
- template<class H, class T> void read(pair<H, T> &p) { cin >> p.first >> p.second; }
- template<class T, size_t S> void read(array<T, S> &a) { for (T &i : a) read(i); }
- template<class T> void read(vector<T> &v) { for (T &i : v) read(i); }
- template<class H, class... T> void read(H &h, T &...t) { read(h); read(t...); }
- /* Output */
- template<class H, class T> ostream &operator<<(ostream &o, pair<H, T> &p) { o << p.first << " " << p.second; return o; }
- template<class T, size_t S> ostream &operator<<(ostream &o, array<T, S> &a) { string s; for (T i : a) o << s << i, s = " "; return o; }
- template<class T> ostream &operator<<(ostream &o, vector<T> &v) { string s; for (T i : v) o << s << i, s = " "; return o; }
- template<class T> void write(T x) { cout << x; }
- template<class H, class... T> void write(const H &h, const T &...t) { write(h); write(t...); }
- void print() { write('\n'); }
- template<class H, class... T> void print(const H &h, const T &...t) { write(h); if (sizeof...(t)) write(' '); print(t...); }
- /* Misc */
- template <typename T> void ckmin(T &a, const T &b) { a = min(a, b); }
- template <typename T> void ckmax(T &a, const T &b) { a = max(a, b); }
- int n, q, s = 1;
- vector<int> adj[MX];
- int sz[MX], in[MX], out[MX], head[MX], dep[MX], par[MX], ind = 0;
- struct node{
- int pu, pd;
- int su, sd;
- int pud, pdu;
- int sud, sdu;
- int rl, rr;
- int ans;
- int zz;
- node(int a){
- rl = rr = a;
- pu = pd = su = sd = pud = pdu = sud = sdu = ans = zz = 1;
- }
- node(){
- pu = pd = su = sd = pud = pdu = sud = sdu = rl = rr = ans = zz = 0;
- }
- void pr(){
- print("p terms", pu, pd, pud, pdu, "\ns terms", su, sd, sud, sdu, "\nother", rl, rr, ans, zz);
- }
- void sw(){
- swap(su, pu);
- swap(sd, pd);
- swap(sdu, pdu);
- swap(sud, pud);
- swap(rr, rl);
- }
- } seg[MX];
- node merge(node a, node b){
- //FerMats Little theorem
- if(a.zz == 0) return b;
- if(b.zz == 0) return a;
- //a + b
- node c = node();
- c.zz = a.zz + b.zz;
- c.rl = a.rl;
- c.rr = b.rr;
- c.pu = (a.pu == a.zz && a.rr <= b.rl) ? a.pu + b.pu : a.pu;
- c.pd = (a.pd == a.zz && a.rr >= b.rl) ? a.pd + b.pd : a.pd;
- c.su = (b.su == b.zz && a.rr >= b.rl) ? b.su + a.su : b.su;
- c.sd = (b.sd == b.zz && a.rr <= b.rl) ? b.sd + a.sd : b.sd;
- c.pud = (a.pud + b.pd * (a.pud == a.zz && a.rr >= b.rl));
- c.pdu = (a.pdu + b.pu * (a.pdu == a.zz && a.rr <= b.rl));
- c.sud = (b.sud + a.sd * (b.sud == b.zz && a.rr <= b.rl));
- c.sdu = (b.sdu + a.su * (b.sdu == b.zz && a.rr >= b.rl));
- if(a.pu == a.zz) c.pud = max(c.pud, a.pu + b.pud * (a.rr <= b.rl));
- if(a.pd == a.zz) c.pdu = max(c.pdu, a.pd + b.pdu * (a.rr >= b.rl));
- if(b.su == b.zz) c.sud = max(c.sud, b.su + a.sud * (a.rr >= b.rl));
- if(b.sd == b.zz) c.sdu = max(c.sdu, b.sd + a.sdu * (a.rr <= b.rl));
- assert(c.pdu >= c.pd);
- //oh boy
- c.ans = max(a.ans, b.ans);
- if(a.rr <= b.rl){ //1 < 2
- c.ans = max({c.ans, a.sdu + b.pu, a.sd + b.pud});
- }else{
- c.ans = max({c.ans, a.sud + b.pd, a.su + b.pdu});
- }
- c.ans = max({c.ans, c.sud, c.sdu, c.pdu, c.pud});
- return c;
- }
- void U(int p, int v, int k, int L, int R){
- if(p < L || R <= p) return ;
- if(L + 1 == R){
- seg[k] = node(v);
- return ;
- }
- int mid = (L + R)/2;
- U(p, v, LC(k), L, mid);
- U(p, v, RC(k), mid, R);
- seg[k] = merge(seg[LC(k)], seg[RC(k)]);
- }
- node S(int qL, int qR, int k, int L, int R){
- if(qR <= L || R <= qL || R <= L) return node();
- if(qL <= L && R <= qR){
- //print("merged", k);
- return seg[k];
- }
- int mid = (L + R)/2;
- return merge(S(qL, qR, LC(k), L, mid), S(qL, qR, RC(k), mid, R));
- }
- void dfs(int x, int p){
- sz[x] = 1;
- dep[x] = dep[p] + 1;
- par[x] = p;
- for(auto &i : adj[x]){
- if(i == p) continue;
- dfs(i, x);
- sz[x] += sz[i];
- if(adj[x][0] == p || sz[i] > sz[adj[x][0]]) swap(adj[x][0], i);
- }
- }
- void dfs2(int x, int p){
- in[x] = ind++;
- for(auto &i : adj[x]){
- if(i == p) continue;
- head[i] = (i == adj[x][0] ? head[x] : i);
- dfs2(i, x);
- }
- out[x] = ind;
- }
- int lca(int a, int b){
- while(head[a] != head[b]){
- if(dep[head[a]] > dep[head[b]]) swap(a, b);
- b = par[head[b]];
- }
- if(dep[a] > dep[b]) swap(a, b);
- return a;
- }
- node go(int a, int b){
- node left = node();
- node right = node();
- int l = lca(a, b);
- //print(a, b, head[a], head[b]);
- while(head[b] != head[l]){
- node c = S(in[head[b]], in[b]+1, 0, 0, s);
- //c.sw();
- right = merge(c, right);
- b = par[head[b]];
- }
- while(head[a] != head[l]){
- node c = S(in[head[a]], in[a]+1, 0, 0, s);
- c.sw();
- left = merge(left, c);
- a = par[head[a]];
- }
- node temp = node();
- if(dep[a] < dep[b]){
- temp = S(in[a], in[b] + 1, 0, 0, s);
- //temp.sw();
- }else{
- temp = S(in[b], in[a] + 1, 0, 0, s);
- temp.sw();
- }
- return merge(left, merge(temp, right));
- }
- void solve(){
- read(n);
- while(s <= n) s*=2;
- for(int i = 2; i<=n; i++){
- int a, b = i; read(a);
- adj[a].push_back(b);
- b[adj].push_back(a);
- }
- dfs(1, 0);
- head[1] = 1;
- dfs2(1, 0);
- for(int i = 1; i<=n; i++){
- U(in[i], i, 0, 0, s);
- }
- read(q);
- ll ans = 0;
- while(q--){
- ll a, b; read(a, b);
- a ^= ans, b ^= ans;
- //print("a", a, b);
- ans = go(a, b).ans;
- print(ans);
- }
- }
- int main(){
- cin.tie(0) -> sync_with_stdio(0);
- int T = 1;
- //cin >> T;
- while(T--){
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement