Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define BOOST ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
- const int N = 2e5+7;
- const int M = 1<<19;
- const int logN = 20;
- int segTree[M];
- void addTree(int v, int value)
- {
- v+=M;
- segTree[v] += value;
- while(v > 1)
- {
- segTree[v/2] += segTree[v];
- v/=2;
- }
- }
- int getSum(int a, int b)
- {
- a += M;
- b += M;
- int res = segTree[a];
- if(a != b)
- res += segTree[b];
- while( a/2 != b/2)
- {
- if(a%2 == 0)
- res += segTree[a+1];
- if(b%2 == 1)
- res += segTree[b-1];
- a/=2;
- b/=2;
- }
- return res;
- }
- vector<int> g[N];
- int depth[N];
- int lcaJumps[N][logN];
- int timeIn[N];
- int timeOut[N];
- void dfsLCA(int v, int pre= -1)
- {
- static int time = 0;
- timeIn[v] = time++;
- lcaJumps[v][0] = pre;
- for(int i = 1;i < logN; ++i)
- {
- if(lcaJumps[v][i-1] == -1)
- lcaJumps[v][i] = -1;
- else
- lcaJumps[v][i] = lcaJumps[lcaJumps[v][i-1]][i-1];
- }
- for(auto u : g[v])
- {
- dfsLCA(u,v);
- }
- timeOut[v] = time++;
- }
- //checks is v is ancestor of u
- bool isAncestor(int v, int u)
- {
- if(v == -1)
- return true;
- if(u == -1)
- return false;
- return timeIn[v] <=timeIn[u] && timeOut[v] >= timeOut[u];
- }
- int lca(int v, int u)
- {
- if(isAncestor(v, u))
- return v;
- if(isAncestor(u,v))
- return u;
- for(int i = logN - 1; i >=0; --i)
- {
- if(!isAncestor(lcaJumps[v][i], u))
- v = lcaJumps[v][i];
- }
- return lcaJumps[v][0];
- }
- int lowestBus[N];
- vector<int> bussesEnds[N];
- int busJumps[N][logN];
- int dfsLowest(int v)
- {
- for(auto u : g[v])
- {
- int res = dfsLowest(u);
- if(depth[res] < depth[lowestBus[v]])
- lowestBus[v] = res;
- }
- return lowestBus[v];
- }
- void dfsBus(int v)
- {
- busJumps[v][0] = lowestBus[v];
- for(int i = 1; i < logN; ++i)
- {
- busJumps[v][i] = busJumps[busJumps[v][i-1]][i-1];
- }
- for(auto u : g[v])
- {
- dfsBus(u);
- }
- }
- //return vertex in tree from which we can go to u in one move
- //second returned value is minimal amount of busses used;
- pair<int,int> getPathtoNearest(int v, int u)
- {
- int cnt = 0;
- for(int i= logN-1; i >=0; --i)
- {
- if(!isAncestor(busJumps[v][i], u))
- {
- cnt += (1<<i);
- v = busJumps[v][i];
- }
- }
- return {v,cnt};
- }
- //checks if there are buses from v to u
- bool reachable(int v,int u)
- {
- for(int i= logN -1 ;i >= 0; --i)
- {
- if(!isAncestor(busJumps[v][i], u))
- v = busJumps[v][i];
- }
- v = busJumps[v][0];
- return isAncestor(v,u);
- }
- vector<pair<int,int>> queriesForVertex[N];
- int segmentCNT[N];
- int result[N];
- void dfsResult(int v)
- {
- cerr<<"akt: "<<v<<' '<<g[v].size()<<'\n';
- for(auto [u,id] : queriesForVertex[v])
- {
- segmentCNT[id] = getSum(timeIn[u], timeOut[u]);
- }
- for(auto u : bussesEnds[v])
- {
- addTree(timeIn[u], 1);
- }
- for(auto u : g[v]
- ) {
- cerr<<"moving from "<<v<<" to "<<u<<" size "<<g[v].size()<<'\n';
- dfsResult(u);
- }
- for(auto [u,id] : queriesForVertex[v])
- {
- if(getSum(timeIn[u], timeOut[u]) > segmentCNT[id])
- --result[id];
- }
- }
- int main()
- {
- BOOST;
- int n;
- cin>>n;
- for(int i = 1;i<n; ++i)
- {
- int a;
- cin>>a;
- --a;
- g[a].push_back(i);
- }
- dfsLCA(0);
- for(int i=0;i<n; ++i)
- {
- cerr<<i<<" : ";
- for(auto u : g[i])
- cerr<<u<<' ';
- cerr<<'\n';
- }
- for(int i = 0;i<n; ++i)
- lowestBus[i] = i;
- cerr<<"lca done\n";
- int q;
- cin>>q;
- for(int i= 0;i<q; ++i)
- {
- int u,v;
- cin>>u>>v;
- --u,--v;
- bussesEnds[u].push_back(v);
- bussesEnds[v].push_back(u);
- int lcaUV = lca(u,v);
- if(depth[lowestBus[u]] > depth[lcaUV])
- lowestBus[u] = lcaUV;
- if(depth[lowestBus[v]] > depth[lcaUV])
- lowestBus[v] = lcaUV;
- }
- cerr<<"busses loaded\n";
- dfsLowest(0);
- dfsBus(0);
- cerr<<"queries\n";
- cin>>q;
- for(int i= 0;i<q; ++i)
- {
- int u,v;
- cin>>u>>v;
- --u,--v;
- int lcaUV = lca(u,v);
- if(! reachable(v, lcaUV) || ! reachable(u,lcaUV))
- {
- result[i] = -1;
- break;
- }
- int lenV, lenU;
- tie(v,lenV) = getPathtoNearest(v, lenV);
- tie(u,lenU) = getPathtoNearest(u,lenU);
- result[i] = lenV +lenU;
- if(v != lcaUV && u != lcaUV)
- {
- queriesForVertex[v].emplace_back(u,i);
- }
- if(u != lcaUV)
- result[i]++;
- if(v != lcaUV)
- result[i]++;
- }
- cerr<<"res dfs\n";
- dfsResult(0);
- cerr<<"end dfs\n";
- for(int i= 0;i<q; ++i)
- cout<<result[i]<<'\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement