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