fork download
copy 
  1.  
  2. import java.io.*;
  3. import java.util.*;
  4.  
  5. public class FearOfTheDark implements Runnable {
  6.  
  7. 	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  8. 	static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
  9. 	static StringTokenizer st = new StringTokenizer("");
  10.  
  11. 	public static String next() {
  12. 		try	{
  13. 		while (!st.hasMoreTokens()) {
  14. 			String s = br.readLine();
  15. 			if (s == null)
  16. 				return null;
  17. 			st = new StringTokenizer(s);
  18. 		}
  19. 		return st.nextToken();
  20. 		}	catch(Exception e)	{
  21. 			return	null;
  22. 		}
  23. 	}
  24. 	public static void main(String[] asda) throws Exception {
  25. 		new Thread(null, new FearOfTheDark(), "Main", 1<<28).run();
  26. 	}
  27. 	public void run() {
  28. 		int N = Integer.parseInt( next() );
  29. 		ArrayList<Integer> [] g = new ArrayList [N];
  30. 		for (int k = 0; k < N; k++)	g[k] = new ArrayList<Integer>();
  31. 		for (int k = 1; k < N; k++)	{
  32. 			int a = Integer.parseInt( next() ) - 1;
  33. 			int b = Integer.parseInt( next() ) - 1;
  34.  
  35. 			g[a].add(b);
  36. 			g[b].add(a);
  37. 		}
  38.  
  39. 		HLD h = new HLD(g);
  40. 	//	h.print(out);
  41.  
  42. 		int M = Integer.parseInt( next() );
  43. 		while	(M-- > 0)	{
  44. 			int q = Integer.parseInt( next() );
  45. 			int a = Integer.parseInt( next() ) - 1;
  46. 			int b = Integer.parseInt( next() ) - 1;
  47.  
  48. 			if (q == 2) {
  49. 				out.println( h.query(a, b) );
  50. 			}	else	{
  51. 				h.update(a, b);
  52. 			}
  53. 		}
  54.         //
  55.         out.flush();
  56.         System.exit(0);
  57.     }
  58.  
  59. }
  60.  
  61. class HLD {
  62. 	private int root;
  63. 	private List<Integer> [] g;
  64.  
  65. 	LCA lca;
  66. 	LazyBinarySegmentTree stree;
  67.  
  68. 	HLD(List<Integer> [] g)	{
  69. 		this.g = g;
  70. 		int N = g.length;
  71.  
  72. 		size = new int [N];
  73. 		parent = new int [N];
  74. 		root = 0;
  75. 		dfs(root, -1);
  76.  
  77. 		numberOfChains = currentIndex = 0;
  78. 		chains = new LinkedList [N];
  79. 		chainHead = new int [N];
  80. 		chainIndex = new int [N];
  81. 		nodeIndex = new int [N];
  82. 		decompose(root);
  83.  
  84. 		lca = new LCA(g, root);
  85. 		stree = new LazyBinarySegmentTree(N);
  86. 	}
  87.  
  88. 	public void update(int a, int b)	{
  89. 		int ancestor = lca.getLCA(a, b);
  90.  
  91. 		mupdate(ancestor, a);
  92. 	//	System.out.println("...");
  93.  
  94. 		mupdate(ancestor, b);
  95. 	//	System.out.println();
  96.  
  97. 		stree.flip( nodeIndex[ancestor], nodeIndex[ancestor] );
  98. 	}
  99.  
  100. 	private void mupdate(int ancestor, int node)	{
  101. 		while	( chainIndex[ancestor] != chainIndex[node] )	{
  102. 			int head = chains[ chainIndex[node] ].get(0);
  103.  
  104. 	//		System.out.printf("updating(%d, %d)\n", nodeIndex[head], nodeIndex[node] );
  105. 			stree.flip(nodeIndex[head], nodeIndex[node]);
  106. 			node = parent[node];
  107. 		}
  108.  
  109. 	//	System.out.printf("updating(%d, %d)\n", nodeIndex[ancestor], nodeIndex[node] );
  110. 		stree.flip( nodeIndex[ancestor], nodeIndex[node] );
  111. 	}
  112.  
  113. 	public int query(int a, int b)	{
  114. 		int ancestor = lca.getLCA(a, b);
  115.  
  116. 		int ans = internalQuery(ancestor, a);
  117. 	//	System.out.println("...");
  118.  
  119. 		ans += internalQuery(ancestor, b);
  120. 	//	System.out.println();
  121.  
  122. 		ans += stree.getFlipped( nodeIndex[ancestor], nodeIndex[ancestor] );
  123.  
  124. 		return ans;
  125. 	}
  126.  
  127. 	private int internalQuery(int ancestor, int node)	{
  128. 		int ans = 0;
  129. 		while	( chainIndex[ancestor] != chainIndex[node] )	{
  130. 			int head = chains[ chainIndex[node] ].get(0);
  131.  
  132. 		//	System.out.printf("query(%d, %d)\n", nodeIndex[head], nodeIndex[node] );
  133. 			ans += stree.getFlipped(nodeIndex[head], nodeIndex[node]);
  134. 			node = parent[node];
  135. 		}
  136.  
  137. 	//	System.out.printf("query(%d, %d)\n", nodeIndex[ancestor], nodeIndex[node] );
  138. 		ans += stree.getFlipped( nodeIndex[ancestor], nodeIndex[node] );
  139. 		return	ans;
  140. 	}
  141.  
  142. 	public void print(PrintWriter out)	{
  143. 		out.println("size: " + Arrays.toString(size) );
  144. 		out.println("chains:");
  145. 		for (int k = 0; k <= numberOfChains; k++)
  146. 			out.println(" " + k + ": " + chains[k] );
  147.  
  148. 		out.println("chainIndex: " + Arrays.toString(chainIndex));
  149. 		out.println("nodeIndex: " + Arrays.toString(nodeIndex));
  150. 	}
  151.  
  152. 	private int numberOfChains;
  153. 	private int currentIndex;
  154. 	private List<Integer> [] chains;	// chains[k] = the list of nodes in the chain k
  155. 	private int [] chainHead;			// chainHead[k] = the head note at chain k
  156. 	private int [] chainIndex;			// chainindex[k] = the chain index where node k belongs
  157. 	private int [] nodeIndex;			// nodeindex[k] = the index assigned to node k after decomposition
  158.  
  159. 	// apply decomposition to a node
  160. 	private void decompose(int node)	{
  161. 		if (chains[numberOfChains] == null) {
  162. 			// this is a new chain
  163. 			chains[numberOfChains] = new LinkedList<Integer>();
  164. 			chainHead[numberOfChains] = node;
  165. 		}
  166. 		chains[numberOfChains].add(node);
  167. 		chainIndex[node] = numberOfChains;
  168. 		nodeIndex[node] = currentIndex++;
  169.  
  170. 	//	System.out.println("decompose " + node);
  171. 		// find the heaviest child
  172. 		int heavyChild = -1;
  173. 		for (int to : g[node])	if (to != parent[node]) {
  174. 			if ( heavyChild == -1 || size[heavyChild] < size[to] ) {
  175. 				heavyChild = to;
  176. 			}
  177. 		}
  178.  
  179. 	//	System.out.println(" heavy child " + heavyChild);
  180.  
  181. 		if (heavyChild == -1) {
  182. 			return;	// this node is a leaf
  183. 		}
  184.  
  185. 		decompose(heavyChild);
  186.  
  187. 		for (int to : g[node])	if (to != parent[node] && to != heavyChild) {
  188. 			// decompose this child into a new chain
  189. 			numberOfChains++;
  190. 			decompose(to);
  191. 		}
  192. 	}
  193.  
  194. 	private int [] size;	// size[k] = size of the subtree rooted at k
  195. 	private int [] parent;	// parent[k] = parent of node k
  196. 	private void dfs(int node, int dad)	{
  197. 		parent[node] = dad;
  198. 		size[node] = 1;
  199. 		for (int to : g[node])	if (dad != to) {
  200. 			dfs(to, node);
  201. 			size[node] += size[to];
  202. 		}
  203. 	}
  204. }
  205.  
  206. class LazyBinarySegmentTree {
  207. 	int [] ones, twos, flip;
  208. 	int size;
  209.  
  210.  
  211. 	public LazyBinarySegmentTree(int size) {
  212. 		size++;
  213. 		int N = 1;
  214. 		while ( (N <<= 1) < size);
  215. 		N <<= 1;
  216.  
  217. 		ones = new int[N];
  218. 		twos = new int[N];
  219. 		flip = new int[N];
  220.  
  221. 		this.size = size;
  222. 	}
  223. 	// x and y sould start in 1
  224. 	void flip(int x, int y)	{
  225. 		x++; y++;
  226. 		update( 1, size, x, y, 1 );
  227. 	//	System.out.printf("update(%d, %d)\n", x, y );
  228. 	}
  229.  
  230. 	int getFlipped(int x, int y)	{
  231. 		x++; y++;
  232. 		// lasta parameter is for the initial status of each element in array (0, 1)
  233. 	//	System.out.printf("query(%d, %d) = %d\n", x, y, query( 1, size, x, y, 1, 1 ) );
  234. 		return	query( 1, size, x, y, 1, 1 );
  235. 	}
  236.  
  237.  
  238. 	private void update(int lo, int hi, int x, int y, int i) {
  239. 		if (x > hi || y < lo)
  240. 			return;
  241.  
  242. 		int mid;
  243. 		if (x <= lo && y >= hi) {
  244. 			ones[i] = (hi - lo + 1) - ones[i];
  245. 			flip[i] += 1;
  246. 			if (flip[i] > 1)
  247. 				flip[i] -= 2;
  248. 			return;
  249. 		}
  250.  
  251. 		mid = (lo + hi) >> 1;
  252. 		update(lo, mid, x, y, 2 * i);
  253. 		update(mid + 1, hi, x, y, 2 * i + 1);
  254.  
  255. 		ones[i] = ones[2 * i] + ones[2 * i + 1];
  256.  
  257. 		if (flip[i] == 1) {
  258. 			ones[i] = (hi - lo + 1) - ones[i];
  259. 		}
  260. 	}
  261.  
  262.  
  263. 	private int query(int lo, int hi, int x, int y, int i, int flag) {
  264. 		if (x > hi || y < lo)
  265. 			return 0;
  266.  
  267. 		if (x <= lo && y >= hi) {
  268. 			if (flag == 1)
  269. 				return ones[i];
  270.  
  271. 			return (hi - lo + 1) - ones[i];
  272. 		}
  273.  
  274.  
  275. 		int mid = (lo + hi) >> 1, nflag = (flag + flip[i]);
  276.  
  277. 		if (nflag > 1)
  278. 			nflag -= 2;
  279.  
  280. 		return	query(lo, mid, x, y, 2 * i, nflag)	+
  281. 				query(mid + 1, hi, x, y, 2 * i + 1, nflag);
  282. 	}
  283.  
  284. }
  285.  
  286.  
  287. class LCA {
  288. 	int N;
  289. 	int logN;
  290. 	int[] dep;
  291. 	int[][] go;
  292. 	List<Integer>[] g;
  293. 	// 1 based index
  294. 	LCA(List<Integer> g[], int root) {
  295. 		this.g = g;
  296. 		N = g.length;
  297. 		logN = 1;
  298. 		while ((1 << logN) <= N)
  299. 			logN++;
  300.  
  301. 	//	System.out.println(N + " " + logN);
  302. 		dep = new int[N];
  303. 		go = new int[N][logN];
  304.  
  305. 		dfs(root, 0, 0);
  306.  
  307. 		// Prepare for LCA queries.
  308. 		for (int k = 1; k < logN; ++k) {
  309. 			for (int i = 1; i < N; ++i) {
  310. 				go[i][k] = go[go[i][k - 1]][k - 1];
  311. 			}
  312. 		}
  313. 	}
  314.  
  315. 	private void dfs(int id, int depth, int dad) {
  316. 		go[id][0] = dad;
  317. 		dep[id] = depth;
  318.  
  319. 		for (int to : g[id]) {
  320. 			if ( to != dad )
  321. 				dfs(to, depth + 1, id);
  322. 		}
  323. 	}
  324.  
  325. 	int getLCA(int u, int v) {
  326. 		if (dep[u] < dep[v]) {
  327. 			int aux = u;
  328. 			u = v;
  329. 			v = aux;
  330. 		}
  331.  
  332. 		int diff = dep[u] - dep[v];
  333. 		for (int i = 0; diff != 0; ++i, diff >>= 1) {
  334. 			if ( (diff & 1) != 0 ) {
  335. 				u = go[u][i];
  336. 			}
  337. 		}
  338.  
  339. 		if (u == v)
  340. 			return u;
  341.  
  342. 		for (int i = logN - 1; i >= 0; --i) {
  343. 			if (go[u][i] != go[v][i]) {
  344. 				u = go[u][i];
  345. 				v = go[v][i];
  346. 			}
  347. 		}
  348. 		return go[u][0];
  349. 	}
  350. }
  351.  
  352.  
  353.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:5: error: class FearOfTheDark is public, should be declared in a file named FearOfTheDark.java
public class FearOfTheDark implements Runnable {
       ^
Note: Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
1 error
stdout
copy 
Standard output is empty
https://ideone.com/G2Ec6P
language:
Java (HotSpot 12)
created:
9 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!