fork download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.DataInputStream;
  4. import java.io.FileInputStream;
  5. import java.io.IOException;
  6. import java.io.BufferedInputStream;
  7. // import java.io.BufferedOutputStream;
  8. // import java.io.PrintWriter;
  9.  
  10. class Main
  11. {
  12. 	static Node[] nodes  ;
  13. 	static Query[] queries ;
  14. 	static int N ;
  15. 	static int M ;
  16. 	static int[] lvl ;
  17. 	static int MAXLVL = 18;
  18. 	static int[][] dp ;
  19. 	static int[] ans ;
  20. 	static int[] dt ;
  21. 	static int[] ID ;
  22. 	static int MAXWT ;
  23. 	static int time ;
  24. 	static boolean[] vis ;
  25. 	static int[] BL ;
  26. 	static int blockSize;
  27. 	static int lnk ;
  28. 	static int wei;
  29. 	static int[] A ;
  30. 	static Node nd;
  31. 	static boolean vi ;
  32.  
  33. 	static class Node{
  34. 		int i ;
  35. 		int st;
  36. 		int en ;
  37. 		List<Integer> links = null;
  38. 		Node(int i){
  39. 			this.i = i ;
  40. 		}
  41. 		public void add(int link){
  42. 			if(links == null){
  43. 				this.links= new ArrayList<Integer>(1) ;
  44. 			}
  45. 			this.links.add(link);
  46. 		}
  47.  
  48. 		public String toString() {
  49. 			return "i = "+i + " st = "+st+" en = "+en+" \n" ;
  50. 		}
  51. 	}
  52. 	static int lca(int u, int v){
  53. 		if(lvl[u] > lvl[v]){
  54. 			u = u+v ;
  55. 			v = u-v;
  56. 			u = u-v ;
  57. 		}
  58. 		int diff = lvl[v]-lvl[u];
  59. 		for(int i=0 ;i<MAXLVL ;i++){
  60. 			if( ((diff >> i)&1) == 1 ){
  61. 				v= dp[v][i];
  62. 			}
  63. 		}
  64. 		if(v ==u){
  65. 			return u ;
  66. 		}
  67.  
  68. 		for(int i= MAXLVL-1 ;i>=0;i--){
  69. 			if(dp[u][i] != dp[v][i]){
  70. 				u= dp[u][i] ;
  71. 				v = dp[v][i];
  72. 			}
  73. 		}
  74. 		return dp[u][0] ;
  75. 	}
  76. 	static class Query implements Comparable<Query>{
  77. 		int id ;
  78. 		int el;
  79. 		int er ;
  80. 		int lca ;
  81. 		public Query(int id, int lca){
  82. 			this.lca = lca;
  83. 			this.id = id ;
  84. 		}
  85. 		public int compareTo(Query q2){
  86. 			if(((this.el-1)/blockSize) != ((q2.el-1)/blockSize)){
  87. 				return this.el- q2.el ;
  88. 			}else{
  89. 				return this.er-q2.er ;
  90. 			}
  91. 		}
  92.  
  93. 		public String toString() {
  94. 			return "id = "+id+" el="+el+" er="+er+" lca="+lca+"\n" ;
  95. 		}
  96. 	}
  97. 	static void dfs(int ind, int level) {
  98. 		if(vis[ind]) {
  99. 			return ;
  100. 		}
  101.  
  102. 		vis[ind] = true ;
  103. 		lvl[ind] = level+1;
  104. 		nodes[ind].st = ++time ;
  105. 		ID[time] = ind ;
  106. 		List<Integer> links = nodes[ind].links;
  107. 		if(links != null) {
  108. 			for(int i =0 ; i< links.size();i++) {
  109. 				lnk = links.get(i) ;
  110. 				if(!vis[lnk]) {
  111. 					dp[lnk][0] = ind ;
  112. 					dfs(lnk, lvl[ind]);
  113. 				}
  114. 			}
  115. 		}
  116. 		nodes[ind].en = ++time ;
  117. 		ID[time] = ind;
  118. 	}
  119. 	static void flattenTree(){
  120.  
  121. 		int time = 1;
  122. 		Stack<Integer> stack = new Stack<Integer>() ;
  123. 		stack.push(1) ;
  124. 		int curr ;
  125. 		boolean[] vis =new boolean[nodes.length];
  126. 		lvl[1] = 0 ;
  127. 		dp[1][0] = 0 ;
  128. 		while(stack.size() != 0){
  129. 			curr = stack.peek() ;
  130. 			if(vis[curr]){
  131. 				nodes[curr].en = time ;
  132.  
  133. 				ID[time++] = curr ;
  134. 				stack.pop() ;
  135. 			}else{
  136. 				nodes[curr].st = time ;
  137. 				ID[time++] = curr ;
  138. 				vis[curr] = true ;
  139. 			}
  140. 			List<Integer> links = nodes[curr].links ;
  141. 			for(int i=0 ;i< links.size() ;i++){
  142. 				int lnk = links.get(i);
  143. 				if(!vis[lnk]){
  144. 					dp[lnk][0] = curr;
  145. 					lvl[lnk] = lvl[curr]+1 ;
  146. 					stack.push(lnk) ;
  147. 				}
  148. 			}
  149.  
  150. 		}
  151.  
  152. 	}
  153. 	static void computeSparseMatrix(){
  154.  
  155. 		for(int i= 1 ;i<MAXLVL;i++){
  156. 			for(int j=1 ;j< N;j++){
  157. //				System.out.println("j = "+j+" i= "+i) ;
  158. 				if(dp[j][i-1] != 0){
  159. 					dp[j][i] = dp[dp[j][i-1]][i-1] ;
  160. 				}
  161. 			}
  162. //			zprint(dp);
  163. 		}
  164. 	}
  165. 	static void moAlgo() throws IOException{
  166. 		int curL = queries[0].el ;
  167. 		int curR = curL-1;
  168. 		int res  = 0 ;
  169. 		vis =new boolean[N+1] ;
  170. 		dt = new int[MAXWT+1];
  171. 		for(int i= 0 ;i<M;i++){
  172. 			while(curL<queries[i].el){
  173. 				res = countdt(ID[curL++], res) ;
  174. 			}
  175. 			while(curL > queries[i].el){
  176. 				res = countdt(ID[--curL], res) ;
  177. 			}
  178. 			while(curR<queries[i].er){
  179. 				res = countdt(ID[++curR], res) ;
  180. 			}
  181. 			while(curR>queries[i].er){
  182. 				res = countdt(ID[curR--], res) ;
  183. 			}
  184. //			int l = ID[curL] ;
  185. //			int r = ID[curR] ;
  186. 			if(queries[i].lca != ID[curL] && queries[i].lca != ID[curR]){
  187. 				res = countdt(queries[i].lca, res) ;
  188. 			}
  189. 			ans[queries[i].id] = res ;
  190. 			if(queries[i].lca != ID[curL] && queries[i].lca != ID[curR]){
  191. 				res = countdt(queries[i].lca, res) ;
  192. 			}
  193. //			System.out.println(queries[i]) ;
  194. 		}
  195. 		// StringBuilder output = new StringBuilder() ;
  196. 		// PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
  197. 		for(int i = 0 ;i<M ;i++){
  198. 			// output.append(ans[i]+"\n") ;
  199.  
  200.  
  201. //			bw.write(ans[i]+"");
  202. 			// bw.newLine(); 
  203. 			System.out.println(ans[i]) ;
  204. 			// out.println(ans[i]);
  205. 		}
  206. 		// out.flush() ;
  207. 		// System.out.print(output) ;
  208. 	}
  209. 	static int countdt(int i, int res) {
  210. //		if(true) {
  211. //			return 1 ;
  212. //		}
  213. 		wei = A[i] ;
  214. 		vi = vis[i];
  215. 		if(vi && (--dt[wei] == 0)){
  216. 			res-- ;	
  217. 		}else if(!vi && (dt[wei]++ == 0) ){
  218. 			res++ ;
  219. 		}
  220. 		vis[i] = vi^true;
  221. 		return res ;
  222. 	}
  223. 	public static void main (String[] args) throws java.lang.Exception
  224. 	{
  225. 		long startTime = System.currentTimeMillis() ;
  226. 		int bytes= 1<<4 ;
  227. 		Reader br =new Reader(); 
  228. 		N = br.nextInt()+1  ;
  229. 		M = br.nextInt()  ;
  230. 		nodes= new Node[N] ;
  231. 		queries = new Query[M] ;
  232. 		vis =new boolean[N] ;
  233. 		dp = new int[N][MAXLVL] ;
  234. 		lvl = new int[N] ;
  235. 		Node nd ;
  236. 		ID = new int[2*N-1] ;
  237. 		MAXWT = 0 ;
  238. 		Map<Integer, Integer> convert =new HashMap<Integer,Integer>(N+100,1f) ;
  239. 		int counter = 0 ;
  240. 		A = new int[N] ;
  241. 		int inp = 0 ;
  242. 		int w = 0 ;
  243. 		for(int i = 1 ;i< N ;i++){
  244. 			w = br.nextInt()  ;
  245. 			if(convert.containsKey(w)) {
  246. 				A[i] = convert.get(w) ; ;
  247. 			}else {
  248. 				convert.put(w, ++counter) ;
  249. 				MAXWT = counter ;
  250. 				A[i] = counter ;
  251. 			}
  252. 			nodes[i] = new Node(i) ;
  253. 		}
  254. 		int u ;
  255. 		int v ;
  256.  
  257. 		for(int i = 0 ;i< N-2 ;i++){
  258. 			u = br.nextInt() ;
  259. 			v = br.nextInt()  ;
  260. 			nodes[u].add(v) ;
  261. 			nodes[v].add(u) ;
  262. 		}
  263. 		time = 0 ;
  264. 		dp[1][0] = 1;
  265. 		dfs(1,0) ;
  266. 		blockSize = 600 ;
  267. 		computeSparseMatrix() ;
  268. 		for(int i= 0 ;i<M;i++){
  269. 			u = br.nextInt()  ;
  270. 			v = br.nextInt()  ;
  271. 			if(nodes[u].st > nodes[v].st){
  272. 				u    = u+v;
  273. 				v = u-v ;
  274. 				u = u-v ;
  275. 			}
  276. 			int lc = lca(u,v) ;
  277. 			Query query = new Query(i,lc) ;
  278. 			if(lc == u){
  279. 				query.el = nodes[u].st ;
  280. 				query.er = nodes[v].st ;
  281. 			}else{
  282. 				query.el = nodes[u].en;
  283. 				query.er = nodes[v].st ;
  284. 			}
  285. 			queries[i] = query ;
  286.  
  287. 		}
  288.  
  289. 		br.close();
  290. 		Arrays.sort(queries) ;
  291. 		ans = new int[M] ;
  292. 		moAlgo();
  293. 	}
  294. 	static void print(int[][] dp) {
  295. 		for(int i= 0 ;i<dp.length ;i++) {
  296. 			System.out.println(Arrays.toString(dp[i])) ;
  297. 		}
  298. 	}
  299. 	static class Reader 
  300.     { 
  301.         final private int BUFFER_SIZE = 1 << 8; 
  302.         private DataInputStream din; 
  303.         private byte[] buffer; 
  304.         private int bufferPointer, bytesRead; 
  305.  
  306.         public Reader() 
  307.         { 
  308.             din = new DataInputStream(new BufferedInputStream(System.in, BUFFER_SIZE)); 
  309.             buffer = new byte[BUFFER_SIZE]; 
  310.             bufferPointer = bytesRead = 0; 
  311.         } 
  312.  
  313.         public Reader(String file_name) throws IOException 
  314.         { 
  315.             din = new DataInputStream(new FileInputStream(file_name)); 
  316.             buffer = new byte[BUFFER_SIZE]; 
  317.             bufferPointer = bytesRead = 0; 
  318.         } 
  319.  
  320.         public String readLine() throws IOException 
  321.         { 
  322.             byte[] buf = new byte[64]; // line length 
  323.             int cnt = 0, c; 
  324.             while ((c = read()) != -1) 
  325.             { 
  326.                 if (c == '\n') 
  327.                     break; 
  328.                 buf[cnt++] = (byte) c; 
  329.             } 
  330.             return new String(buf, 0, cnt); 
  331.         } 
  332.  
  333.         public int nextInt() throws IOException 
  334.         { 
  335.             int ret = 0; 
  336.             byte c = read(); 
  337.             while (c <= ' ') 
  338.                 c = read(); 
  339.             boolean neg = (c == '-'); 
  340.             if (neg) 
  341.                 c = read(); 
  342.             do
  343.             { 
  344.                 ret = ret * 10 + c - '0'; 
  345.             }  while ((c = read()) >= '0' && c <= '9'); 
  346.  
  347.             if (neg) 
  348.                 return -ret; 
  349.             return ret; 
  350.         } 
  351.  
  352.         public long nextLong() throws IOException 
  353.         { 
  354.             long ret = 0; 
  355.             byte c = read(); 
  356.             while (c <= ' ') 
  357.                 c = read(); 
  358.             boolean neg = (c == '-'); 
  359.             if (neg) 
  360.                 c = read(); 
  361.             do { 
  362.                 ret = ret * 10 + c - '0'; 
  363.             } 
  364.             while ((c = read()) >= '0' && c <= '9'); 
  365.             if (neg) 
  366.                 return -ret; 
  367.             return ret; 
  368.         } 
  369.  
  370.         public double nextDouble() throws IOException 
  371.         { 
  372.             double ret = 0, div = 1; 
  373.             byte c = read(); 
  374.             while (c <= ' ') 
  375.                 c = read(); 
  376.             boolean neg = (c == '-'); 
  377.             if (neg) 
  378.                 c = read(); 
  379.  
  380.             do { 
  381.                 ret = ret * 10 + c - '0'; 
  382.             } 
  383.             while ((c = read()) >= '0' && c <= '9'); 
  384.  
  385.             if (c == '.') 
  386.             { 
  387.                 while ((c = read()) >= '0' && c <= '9') 
  388.                 { 
  389.                     ret += (c - '0') / (div *= 10); 
  390.                 } 
  391.             } 
  392.  
  393.             if (neg) 
  394.                 return -ret; 
  395.             return ret; 
  396.         } 
  397.  
  398.         private void fillBuffer() throws IOException 
  399.         { 
  400.             bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE); 
  401.             if (bytesRead == -1) 
  402.                 buffer[0] = -1; 
  403.         } 
  404.  
  405.         private byte read() throws IOException 
  406.         { 
  407.             if (bufferPointer == bytesRead) 
  408.                 fillBuffer(); 
  409.             return buffer[bufferPointer++]; 
  410.         } 
  411.  
  412.         public void close() throws IOException 
  413.         { 
  414.             if (din == null) 
  415.                 return; 
  416.             din.close(); 
  417.         } 
  418.     } 
  419.  
  420. }
Success #stdin #stdout 0.06s 32916KB
comments (?)
stdin
copy 
20 10
14 11 7 11 11 3 18 9 6 5 15 10 17 2 3 8 7 6 9 7
2 12
2 13
13 5
12 19
5 17
12 15
15 3
19 18
12 14
18 4
5 9
14 1
13 11
15 6
5 8
19 7
19 10
10 16
3 20
9 13
5 6
9 16
18 11
2 3
11 12
1 10
2 4
9 17
3 8
stdout
copy 
3
4
7
6
4
4
5
4
3
6
https://ideone.com/YE0hZg
problem COT2, based on SPOJ submission 25822974 (JAVA), 2020-04-22 09:08:36
language:
Java (HotSpot 12)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!