fork download
copy 
  1. import java.io.*;
  2. import java.util.ArrayList;
  3. import java.util.Arrays;
  4. import java.util.Collections;
  5. import java.util.Comparator;
  6. import java.util.HashMap;
  7. import java.util.StringTokenizer;
  8.  
  9.  
  10. public class Main{
  11. 	public static final int mod = 1000000007;
  12. 	public static ArrayList<Integer> adj[];
  13. 	public static int w[],a[],st[],et[],par[][],depth[],occ[],cnt[],time,sum;
  14. 	public static int N = 40011;
  15. 	public static void main(String[] args)throws IOException {
  16. 		// TODO Auto-generated method stub
  17. 		InputStream input = System.in;
  18. 		Reader in  = new Reader();
  19. 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  20.  
  21. 		int n = in.nextInt();
  22. 		int m = in.nextInt();
  23.  
  24. 		sum = time = 0;
  25. 		adj = new ArrayList[N];
  26. 		w = new int[N];
  27. 		st = new int[N];
  28. 		et = new int[N];
  29. 		a = new int[2*N];
  30. 		par = new int[N][16];
  31. 		depth = new int[N];
  32. 		int block = (int)Math.sqrt(n);
  33.  
  34. 		HashMap<Integer,Integer> hash = new HashMap<Integer,Integer>();
  35.  
  36. 		for(int i=0; i<N; i++)
  37. 			adj[i] = new ArrayList<Integer>();
  38.  
  39. 		int no = 0;
  40. 		for(int i=1; i<=n; i++)
  41. 			{
  42. 				int tmp = in.nextInt();
  43. 				if(!hash.containsKey(tmp))
  44. 				{
  45. 					hash.put(tmp,++no);
  46. 				}
  47. 				w[i] = hash.get(tmp);
  48. 			}
  49.  
  50. 		for(int i=0; i<n-1; i++)
  51. 		{
  52. 			int u = in.nextInt();
  53. 			int v = in.nextInt();
  54. 			adj[u].add(v);
  55. 			adj[v].add(u);
  56. 		}
  57.  
  58. 		for(int i=0; i<16; i++)
  59. 			for(int j=1; j<=n; j++)
  60. 				par[j][i] = -1;
  61.  
  62. 		depth[1] = 0;
  63. 		dfs(1,0);
  64.  
  65. 		for(int i=1; i<16; i++)
  66. 			for(int j=1; j<=n; j++)
  67. 				{
  68. 				if(par[j][i-1] != -1)
  69. 					par[j][i] = par[par[j][i-1]][i-1];
  70. 				}
  71.  
  72.  
  73. 		Query q[] = new Query[m];
  74. 		int ans[] = new int[m];
  75.  
  76. 		for(int i=0; i<m; i++)
  77. 		{
  78. 			int u = in.nextInt();
  79. 			int v = in.nextInt();
  80.  
  81. 			if (depth [u] < depth[v])
  82. 				{
  83. 					int tmp = u;
  84. 					u = v;
  85. 					v = tmp;
  86. 				}
  87. 			int lc = lca(u, v);
  88. 			if (lc == v)
  89. 			{
  90. 				q[i] = new Query(st[v],st[u]+1,i,-1);
  91. 			}
  92. 			else{
  93. 				if (st[v] > et[u])
  94. 				{	
  95. 					q[i] = new Query(et[u],st[v]+1,i,lc);
  96. 				}
  97. 				else
  98. 				{
  99. 					q[i] = new Query(et[v],st[u]+1,i,lc);
  100. 				}
  101. 			}
  102.  
  103. 		}
  104.  
  105.  
  106.  
  107. 		Arrays.sort(q,new Comparator<Query>(){
  108.  
  109. 			public int compare(Query q1,Query q2)
  110. 			{
  111. 				if(q1.l/block < q2.l/block)
  112. 					return -1;
  113. 				else if(q1.l/block > q2.l/block)
  114. 					return 1;
  115. 				else
  116. 					return q1.r-q2.r;
  117. 			}
  118.  
  119. 		});
  120.  
  121. 		occ = new int[N];
  122. 		cnt = new int[N];
  123. 		sum = 0;
  124.  
  125. 		int L = 0, R = 0;
  126. 		StringBuilder sb = new StringBuilder("");
  127. 		for(int i=0; i<m; i++)
  128. 		{
  129.  
  130. 			int nextL = q[i].l;
  131. 			int nextR = q[i].r;
  132.  
  133. 			while(L < nextL)
  134. 			{
  135. 				remove(a[L]);
  136. 				L++;
  137. 			}
  138.  
  139. 			while(L > nextL)
  140. 			{
  141. 				add(a[L-1]);
  142. 				L--;
  143. 			}
  144.  
  145.  
  146. 			while(R < nextR)
  147. 			{
  148. 				add(a[R]);
  149. 				R++;	
  150. 			}
  151.  
  152. 			while(R > nextR )
  153. 			{
  154. 				remove(a[R-1]);
  155. 				R--;
  156. 			}
  157.  
  158.  
  159. 			if(q[i].lca != -1 && cnt[w[q[i].lca]] == 0)
  160. 			{
  161. 				ans[q[i].i] = sum+1;
  162. 			}
  163. 			else
  164. 			{
  165. 				ans[q[i].i] = sum;
  166. 			}
  167.  
  168. 		}
  169. 		for(int i=0; i<m; i++)
  170. 			sb.append(ans[i]+"\n");
  171.  
  172. 		System.out.println(sb.toString());
  173.  
  174. 	}
  175. 	static void remove(int x)
  176. 	{	
  177.  
  178. 		int wt = w[x];
  179. 		occ[x]--;
  180.  
  181. 		if (occ[x] == 1){
  182. 			cnt[wt]++;
  183. 			if (cnt[wt] == 1)
  184. 				sum++;
  185. 			return;
  186. 		}
  187. 		cnt[wt]--;
  188. 		if (cnt[wt] == 0) sum--;
  189.  
  190. 	}
  191. 	static void add(int x)
  192. 	{	
  193.  
  194. 		occ[x]++;
  195. 		cnt[w[x]]++;
  196. 		if (occ[x] == 2){
  197. 			cnt[w[x]] -= 2;
  198. 			if (cnt[w[x]] == 0)
  199. 				sum--;
  200. 		}
  201. 		else if (cnt[w[x]] == 1) sum++;
  202.  
  203.  
  204. 	}
  205.  
  206. 	static class Query{
  207. 		int l,r,i,lca;
  208.  
  209. 		Query(int l,int r,int i,int lca)
  210. 		{
  211. 			this.lca = lca;
  212. 			this.l = l;
  213. 			this.r = r;
  214. 			this.i = i;
  215. 		}
  216. 	}
  217.  
  218. 	static int lca(int u,int v)
  219. 	{
  220. 		int lg, i;
  221. 		for (lg = 0; (1<<lg) <= depth[u]; lg++);
  222. 		lg--;
  223. 		for(i=lg; i>=0; i--)
  224. 			if ( depth[u] - (1<<i) >= depth[v])
  225. 				u = par[u][i];
  226. 		if (u == v)
  227. 			return u;
  228. 		for(i = lg; i >= 0; i--){
  229. 			if (par[u][i] != -1 && par[u][i] != par[v][i])
  230. 			{	u = par[u][i]; v = par[v][i];}
  231. 		}
  232. 		return par[u][0];
  233. 	}
  234.  
  235. 	static void dfs(int curr,int prev)
  236. 	{
  237. 		st[curr] = ++time;
  238. 		a[time] = curr;
  239.  
  240.  
  241.  
  242. 		for(int i=0; i<adj[curr].size(); i++)
  243. 		{
  244. 			int next = adj[curr].get(i);
  245. 			if(next != prev)
  246. 				{
  247. 				depth[next] = depth[curr]+1;
  248. 				par[next][0] = curr;
  249. 				dfs(next,curr);
  250. 				}
  251. 		}
  252.  
  253. 		et[curr] = ++time;
  254. 		a[time] = curr;
  255.  
  256. 	}
  257.  
  258.  
  259. 	static double dist(double x1,double y1,double x2,double y2)
  260. 	{
  261. 		return Math.sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
  262.  
  263. 	}
  264. 	static long modpowIter(long a, long b, long c) {
  265.         long ans=1;
  266.         while(b != 0) {
  267.                 if(b%2 == 1)
  268.                         ans=(ans*a)%c;
  269.  
  270.                 a=(a*a)%c;
  271.                 b /= 2;
  272.         }
  273.         return ans;
  274. }
  275.  
  276. static int gcd(int a,int b)
  277. {
  278. 	if(b == 0)
  279. 		return a;
  280. 	else return gcd(b,a%b);
  281. }
  282. static int lcm(int a, int b)
  283. {
  284.  
  285. 	return (a*b)/gcd(a,b);
  286. }
  287. 	 static class Reader
  288. 	    {
  289. 	        final private int BUFFER_SIZE = 1 << 16;
  290. 	        private DataInputStream din;
  291. 	        private byte[] buffer;
  292. 	        private int bufferPointer, bytesRead;
  293.  
  294. 	        public Reader()
  295. 	        {
  296. 	            din = new DataInputStream(System.in);
  297. 	            buffer = new byte[BUFFER_SIZE];
  298. 	            bufferPointer = bytesRead = 0;
  299. 	        }
  300.  
  301. 	        public Reader(String file_name) throws IOException
  302. 	        {
  303. 	            din = new DataInputStream(new FileInputStream(file_name));
  304. 	            buffer = new byte[BUFFER_SIZE];
  305. 	            bufferPointer = bytesRead = 0;
  306. 	        }
  307.  
  308. 	        public String readLine() throws IOException
  309. 	        {
  310. 	            byte[] buf = new byte[64]; // line length
  311. 	            int cnt = 0, c;
  312. 	            while ((c = read()) != -1)
  313. 	            {
  314. 	                if (c == '\n')
  315. 	                    break;
  316. 	                buf[cnt++] = (byte) c;
  317. 	            }
  318. 	            return new String(buf, 0, cnt);
  319. 	        }
  320.  
  321. 	        public int nextInt() throws IOException
  322. 	        {
  323. 	            int ret = 0;
  324. 	            byte c = read();
  325. 	            while (c <= ' ')
  326. 	                c = read();
  327. 	            boolean neg = (c == '-');
  328. 	            if (neg)
  329. 	                c = read();
  330. 	            do
  331. 	            {
  332. 	                ret = ret * 10 + c - '0';
  333. 	            }  while ((c = read()) >= '0' && c <= '9');
  334.  
  335. 	            if (neg)
  336. 	                return -ret;
  337. 	            return ret;
  338. 	        }
  339.  
  340. 	        public long nextLong() throws IOException
  341. 	        {
  342. 	            long ret = 0;
  343. 	            byte c = read();
  344. 	            while (c <= ' ')
  345. 	                c = read();
  346. 	            boolean neg = (c == '-');
  347. 	            if (neg)
  348. 	                c = read();
  349. 	            do {
  350. 	                ret = ret * 10 + c - '0';
  351. 	            }
  352. 	            while ((c = read()) >= '0' && c <= '9');
  353. 	            if (neg)
  354. 	                return -ret;
  355. 	            return ret;
  356. 	        }
  357.  
  358. 	        public double nextDouble() throws IOException
  359. 	        {
  360. 	            double ret = 0, div = 1;
  361. 	            byte c = read();
  362. 	            while (c <= ' ')
  363. 	                c = read();
  364. 	            boolean neg = (c == '-');
  365. 	            if (neg)
  366. 	                c = read();
  367.  
  368. 	            do {
  369. 	                ret = ret * 10 + c - '0';
  370. 	            }
  371. 	            while ((c = read()) >= '0' && c <= '9');
  372.  
  373. 	            if (c == '.')
  374. 	            {
  375. 	                while ((c = read()) >= '0' && c <= '9')
  376. 	                {
  377. 	                    ret += (c - '0') / (div *= 10);
  378. 	                }
  379. 	            }
  380.  
  381. 	            if (neg)
  382. 	                return -ret;
  383. 	            return ret;
  384. 	        }
  385.  
  386. 	        private void fillBuffer() throws IOException
  387. 	        {
  388. 	            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
  389. 	            if (bytesRead == -1)
  390. 	                buffer[0] = -1;
  391. 	        }
  392.  
  393. 	        private byte read() throws IOException
  394. 	        {
  395. 	            if (bufferPointer == bytesRead)
  396. 	                fillBuffer();
  397. 	            return buffer[bufferPointer++];
  398. 	        }
  399.  
  400. 	        public void close() throws IOException
  401. 	        {
  402. 	            if (din == null)
  403. 	                return;
  404. 	            din.close();
  405. 	        }
  406. 	    }
  407. }
Runtime error #stdin #stdout #stderr 0.06s 4386816KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 65536
	at Main$Reader.read(Main.java:397)
	at Main$Reader.nextInt(Main.java:326)
	at Main.main(Main.java:21)
https://ideone.com/PQUMR6
language:
Java (HotSpot 12)
created:
6 years ago
visibility:
public

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!