Advertisement
Guest User

Untitled

a guest
Mar 23rd, 2019
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.31 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define BOOST ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
  5.  
  6. const int N = 2e5+7;
  7. const int M = 1<<19;
  8. const int logN = 20;
  9.  
  10. int segTree[M];
  11.  
  12. void addTree(int v, int value)
  13. {
  14. v+=M;
  15. segTree[v] += value;
  16. while(v > 1)
  17. {
  18. segTree[v/2] += segTree[v];
  19. v/=2;
  20. }
  21. }
  22.  
  23. int getSum(int a, int b)
  24. {
  25. a += M;
  26. b += M;
  27.  
  28. int res = segTree[a];
  29. if(a != b)
  30. res += segTree[b];
  31.  
  32. while( a/2 != b/2)
  33. {
  34. if(a%2 == 0)
  35. res += segTree[a+1];
  36. if(b%2 == 1)
  37. res += segTree[b-1];
  38.  
  39. a/=2;
  40. b/=2;
  41. }
  42. return res;
  43. }
  44.  
  45. vector<int> g[N];
  46. int depth[N];
  47. int lcaJumps[N][logN];
  48. int timeIn[N];
  49. int timeOut[N];
  50.  
  51. void dfsLCA(int v, int pre= -1)
  52. {
  53. static int time = 0;
  54.  
  55. timeIn[v] = time++;
  56. lcaJumps[v][0] = pre;
  57.  
  58. for(int i = 1;i < logN; ++i)
  59. {
  60. if(lcaJumps[v][i-1] == -1)
  61. lcaJumps[v][i] = -1;
  62. else
  63. lcaJumps[v][i] = lcaJumps[lcaJumps[v][i-1]][i-1];
  64. }
  65.  
  66. for(auto u : g[v])
  67. {
  68. dfsLCA(u,v);
  69. }
  70.  
  71. timeOut[v] = time++;
  72. }
  73.  
  74.  
  75. //checks is v is ancestor of u
  76. bool isAncestor(int v, int u)
  77. {
  78. if(v == -1)
  79. return true;
  80. if(u == -1)
  81. return false;
  82.  
  83. return timeIn[v] <=timeIn[u] && timeOut[v] >= timeOut[u];
  84. }
  85.  
  86. int lca(int v, int u)
  87. {
  88. if(isAncestor(v, u))
  89. return v;
  90. if(isAncestor(u,v))
  91. return u;
  92.  
  93. for(int i = logN - 1; i >=0; --i)
  94. {
  95. if(!isAncestor(lcaJumps[v][i], u))
  96. v = lcaJumps[v][i];
  97. }
  98. return lcaJumps[v][0];
  99. }
  100.  
  101. int lowestBus[N];
  102. vector<int> bussesEnds[N];
  103. int busJumps[N][logN];
  104.  
  105.  
  106. int dfsLowest(int v)
  107. {
  108. for(auto u : g[v])
  109. {
  110. int res = dfsLowest(u);
  111. if(depth[res] < depth[lowestBus[v]])
  112. lowestBus[v] = res;
  113. }
  114. return lowestBus[v];
  115. }
  116.  
  117. void dfsBus(int v)
  118. {
  119. busJumps[v][0] = lowestBus[v];
  120.  
  121. for(int i = 1; i < logN; ++i)
  122. {
  123. busJumps[v][i] = busJumps[busJumps[v][i-1]][i-1];
  124. }
  125.  
  126. for(auto u : g[v])
  127. {
  128. dfsBus(u);
  129. }
  130. }
  131.  
  132. //return vertex in tree from which we can go to u in one move
  133. //second returned value is minimal amount of busses used;
  134. pair<int,int> getPathtoNearest(int v, int u)
  135. {
  136. int cnt = 0;
  137.  
  138. for(int i= logN-1; i >=0; --i)
  139. {
  140. if(!isAncestor(busJumps[v][i], u))
  141. {
  142. cnt += (1<<i);
  143. v = busJumps[v][i];
  144. }
  145. }
  146.  
  147. return {v,cnt};
  148. }
  149.  
  150.  
  151. //checks if there are buses from v to u
  152. bool reachable(int v,int u)
  153. {
  154. for(int i= logN -1 ;i >= 0; --i)
  155. {
  156. if(!isAncestor(busJumps[v][i], u))
  157. v = busJumps[v][i];
  158. }
  159. v = busJumps[v][0];
  160. return isAncestor(v,u);
  161. }
  162.  
  163. vector<pair<int,int>> queriesForVertex[N];
  164.  
  165. int segmentCNT[N];
  166. int result[N];
  167.  
  168. void dfsResult(int v)
  169. {
  170. cerr<<"akt: "<<v<<' '<<g[v].size()<<'\n';
  171. for(auto [u,id] : queriesForVertex[v])
  172. {
  173. segmentCNT[id] = getSum(timeIn[u], timeOut[u]);
  174. }
  175.  
  176. for(auto u : bussesEnds[v])
  177. {
  178. addTree(timeIn[u], 1);
  179. }
  180.  
  181.  
  182. for(auto u : g[v]
  183. ) {
  184. cerr<<"moving from "<<v<<" to "<<u<<" size "<<g[v].size()<<'\n';
  185. dfsResult(u);
  186. }
  187.  
  188. for(auto [u,id] : queriesForVertex[v])
  189. {
  190. if(getSum(timeIn[u], timeOut[u]) > segmentCNT[id])
  191. --result[id];
  192. }
  193. }
  194.  
  195. int main()
  196. {
  197. BOOST;
  198.  
  199. int n;
  200. cin>>n;
  201.  
  202. for(int i = 1;i<n; ++i)
  203. {
  204. int a;
  205. cin>>a;
  206. --a;
  207. g[a].push_back(i);
  208. }
  209. dfsLCA(0);
  210.  
  211. for(int i=0;i<n; ++i)
  212. {
  213. cerr<<i<<" : ";
  214. for(auto u : g[i])
  215. cerr<<u<<' ';
  216. cerr<<'\n';
  217. }
  218.  
  219. for(int i = 0;i<n; ++i)
  220. lowestBus[i] = i;
  221.  
  222. cerr<<"lca done\n";
  223. int q;
  224. cin>>q;
  225. for(int i= 0;i<q; ++i)
  226. {
  227. int u,v;
  228. cin>>u>>v;
  229. --u,--v;
  230.  
  231. bussesEnds[u].push_back(v);
  232. bussesEnds[v].push_back(u);
  233.  
  234. int lcaUV = lca(u,v);
  235.  
  236. if(depth[lowestBus[u]] > depth[lcaUV])
  237. lowestBus[u] = lcaUV;
  238.  
  239.  
  240. if(depth[lowestBus[v]] > depth[lcaUV])
  241. lowestBus[v] = lcaUV;
  242. }
  243.  
  244. cerr<<"busses loaded\n";
  245. dfsLowest(0);
  246. dfsBus(0);
  247.  
  248. cerr<<"queries\n";
  249. cin>>q;
  250. for(int i= 0;i<q; ++i)
  251. {
  252. int u,v;
  253. cin>>u>>v;
  254. --u,--v;
  255.  
  256. int lcaUV = lca(u,v);
  257.  
  258. if(! reachable(v, lcaUV) || ! reachable(u,lcaUV))
  259. {
  260. result[i] = -1;
  261. break;
  262. }
  263.  
  264. int lenV, lenU;
  265.  
  266. tie(v,lenV) = getPathtoNearest(v, lenV);
  267. tie(u,lenU) = getPathtoNearest(u,lenU);
  268.  
  269. result[i] = lenV +lenU;
  270.  
  271. if(v != lcaUV && u != lcaUV)
  272. {
  273. queriesForVertex[v].emplace_back(u,i);
  274. }
  275.  
  276. if(u != lcaUV)
  277. result[i]++;
  278.  
  279. if(v != lcaUV)
  280. result[i]++;
  281. }
  282. cerr<<"res dfs\n";
  283. dfsResult(0);
  284. cerr<<"end dfs\n";
  285. for(int i= 0;i<q; ++i)
  286. cout<<result[i]<<'\n';
  287.  
  288. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement