Artifact df81a86e707e972b64432cf012947003249a8816:
0000: 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d //--------------
0010: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0020: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0030: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0d ---------------.
0040: 0a 2f 2f 20 54 68 65 20 4c 65 61 73 74 20 43 6f .// The Least Co
0050: 6d 6d 6f 6e 20 41 6e 63 65 73 74 6f 72 0d 0a 2f mmon Ancestor../
0060: 2f 0d 0a 2f 2f 20 56 65 72 69 66 69 65 64 20 62 /..// Verified b
0070: 79 0d 0a 2f 2f 20 20 20 2d 20 49 43 50 43 20 32 y..// - ICPC 2
0080: 30 32 31 20 59 6f 6b 6f 68 61 6d 61 20 52 65 67 021 Yokohama Reg
0090: 69 6f 6e 61 6c 20 49 0d 0a 2f 2f 2d 2d 2d 2d 2d ional I..//-----
00a0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00b0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00d0: 2d 2d 2d 2d 2d 2d 2d 2d 0d 0a 0d 0a 0d 0a 74 65 --------......te
00e0: 6d 70 6c 61 74 65 3c 69 6e 74 20 4b 3d 31 37 3e mplate<int K=17>
00f0: 0d 0a 73 74 72 75 63 74 20 4c 63 61 0d 0a 7b 0d ..struct Lca..{.
0100: 0a 09 63 6f 6e 73 74 20 69 6e 74 20 4e 3b 0d 0a ..const int N;..
0110: 09 63 6f 6e 73 74 20 76 65 63 74 6f 72 3c 69 6e .const vector<in
0120: 74 3e 26 20 64 65 70 74 68 3b 0d 0a 09 76 65 63 t>& depth;...vec
0130: 74 6f 72 3c 76 65 63 74 6f 72 3c 69 6e 74 3e 3e tor<vector<int>>
0140: 20 6a 75 6d 70 3b 0d 0a 09 4c 63 61 28 69 6e 74 jump;...Lca(int
0150: 20 4e 2c 20 63 6f 6e 73 74 20 76 65 63 74 6f 72 N, const vector
0160: 3c 69 6e 74 3e 26 20 70 61 72 65 6e 74 2c 20 63 <int>& parent, c
0170: 6f 6e 73 74 20 76 65 63 74 6f 72 3c 69 6e 74 3e onst vector<int>
0180: 26 20 64 65 70 74 68 29 0d 0a 09 09 3a 20 4e 28 & depth)....: N(
0190: 4e 29 2c 20 64 65 70 74 68 28 64 65 70 74 68 29 N), depth(depth)
01a0: 2c 20 6a 75 6d 70 28 4b 2c 20 76 65 63 74 6f 72 , jump(K, vector
01b0: 3c 69 6e 74 3e 28 4e 2c 20 2d 31 29 29 0d 0a 09 <int>(N, -1))...
01c0: 7b 0d 0a 09 09 6a 75 6d 70 5b 30 5d 20 3d 20 70 {....jump[0] = p
01d0: 61 72 65 6e 74 3b 0d 0a 09 09 66 6f 72 28 69 6e arent;....for(in
01e0: 74 20 6b 3d 30 3b 20 6b 2b 31 3c 4b 3b 20 2b 2b t k=0; k+1<K; ++
01f0: 6b 29 0d 0a 09 09 66 6f 72 28 69 6e 74 20 76 3d k)....for(int v=
0200: 30 3b 20 76 3c 4e 3b 20 2b 2b 76 29 0d 0a 09 09 0; v<N; ++v)....
0210: 09 69 66 28 6a 75 6d 70 5b 6b 5d 5b 76 5d 20 21 .if(jump[k][v] !
0220: 3d 20 2d 31 29 0d 0a 09 09 09 09 6a 75 6d 70 5b = -1)......jump[
0230: 6b 2b 31 5d 5b 76 5d 20 3d 20 6a 75 6d 70 5b 6b k+1][v] = jump[k
0240: 5d 5b 6a 75 6d 70 5b 6b 5d 5b 76 5d 5d 3b 0d 0a ][jump[k][v]];..
0250: 09 7d 0d 0a 0d 0a 09 69 6e 74 20 6f 70 65 72 61 .}.....int opera
0260: 74 6f 72 28 29 28 69 6e 74 20 61 2c 20 69 6e 74 tor()(int a, int
0270: 20 62 29 20 63 6f 6e 73 74 20 7b 0d 0a 09 09 69 b) const {....i
0280: 66 28 64 65 70 74 68 5b 61 5d 3e 64 65 70 74 68 f(depth[a]>depth
0290: 5b 62 5d 29 20 73 77 61 70 28 61 2c 62 29 3b 0d [b]) swap(a,b);.
02a0: 0a 09 09 66 6f 72 28 69 6e 74 20 6b 3d 30 3b 20 ...for(int k=0;
02b0: 6b 3c 4b 3b 20 2b 2b 6b 29 0d 0a 09 09 09 69 66 k<K; ++k).....if
02c0: 28 28 64 65 70 74 68 5b 62 5d 2d 64 65 70 74 68 ((depth[b]-depth
02d0: 5b 61 5d 29 20 26 20 28 31 3c 3c 6b 29 29 0d 0a [a]) & (1<<k))..
02e0: 09 09 09 09 62 20 3d 20 6a 75 6d 70 5b 6b 5d 5b ....b = jump[k][
02f0: 62 5d 3b 0d 0a 09 09 69 66 28 61 20 3d 3d 20 62 b];....if(a == b
0300: 29 0d 0a 09 09 09 72 65 74 75 72 6e 20 61 3b 0d ).....return a;.
0310: 0a 09 09 66 6f 72 28 69 6e 74 20 6b 3d 4b 2d 31 ...for(int k=K-1
0320: 3b 20 6b 3e 3d 30 3b 20 2d 2d 6b 29 0d 0a 09 09 ; k>=0; --k)....
0330: 09 69 66 28 6a 75 6d 70 5b 6b 5d 5b 61 5d 20 21 .if(jump[k][a] !
0340: 3d 20 6a 75 6d 70 5b 6b 5d 5b 62 5d 29 20 7b 0d = jump[k][b]) {.
0350: 0a 09 09 09 09 61 20 3d 20 6a 75 6d 70 5b 6b 5d .....a = jump[k]
0360: 5b 61 5d 3b 0d 0a 09 09 09 09 62 20 3d 20 6a 75 [a];......b = ju
0370: 6d 70 5b 6b 5d 5b 62 5d 3b 0d 0a 09 09 09 7d 0d mp[k][b];.....}.
0380: 0a 09 09 72 65 74 75 72 6e 20 6a 75 6d 70 5b 30 ...return jump[0
0390: 5d 5b 61 5d 3b 0d 0a 09 7d 0d 0a 7d 3b 0d 0a ][a];...}..};..