0000: 23 69 6e 63 6c 75 64 65 20 3c 69 6f 73 74 72 65 #include <iostre
0010: 61 6d 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 73 am>..#include <s
0020: 73 74 72 65 61 6d 3e 0d 0a 23 69 6e 63 6c 75 64 stream>..#includ
0030: 65 20 3c 69 6f 6d 61 6e 69 70 3e 0d 0a 23 69 6e e <iomanip>..#in
0040: 63 6c 75 64 65 20 3c 76 65 63 74 6f 72 3e 0d 0a clude <vector>..
0050: 23 69 6e 63 6c 75 64 65 20 3c 73 74 72 69 6e 67 #include <string
0060: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 6d 61 70 >..#include <map
0070: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 73 65 74 >..#include <set
0080: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 61 6c 67 >..#include <alg
0090: 6f 72 69 74 68 6d 3e 0d 0a 23 69 6e 63 6c 75 64 orithm>..#includ
00a0: 65 20 3c 6e 75 6d 65 72 69 63 3e 0d 0a 23 69 6e e <numeric>..#in
00b0: 63 6c 75 64 65 20 3c 69 74 65 72 61 74 6f 72 3e clude <iterator>
00c0: 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 66 75 6e 63 ..#include <func
00d0: 74 69 6f 6e 61 6c 3e 0d 0a 23 69 6e 63 6c 75 64 tional>..#includ
00e0: 65 20 3c 63 6f 6d 70 6c 65 78 3e 0d 0a 23 69 6e e <complex>..#in
00f0: 63 6c 75 64 65 20 3c 71 75 65 75 65 3e 0d 0a 23 clude <queue>..#
0100: 69 6e 63 6c 75 64 65 20 3c 73 74 61 63 6b 3e 0d include <stack>.
0110: 0a 23 69 6e 63 6c 75 64 65 20 3c 63 6d 61 74 68 .#include <cmath
0120: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 63 61 73 >..#include <cas
0130: 73 65 72 74 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 sert>..#include
0140: 3c 74 75 70 6c 65 3e 0d 0a 75 73 69 6e 67 20 6e <tuple>..using n
0150: 61 6d 65 73 70 61 63 65 20 73 74 64 3b 0d 0a 74 amespace std;..t
0160: 79 70 65 64 65 66 20 6c 6f 6e 67 20 6c 6f 6e 67 ypedef long long
0170: 20 4c 4c 3b 0d 0a 74 79 70 65 64 65 66 20 63 6f LL;..typedef co
0180: 6d 70 6c 65 78 3c 64 6f 75 62 6c 65 3e 20 43 4d mplex<double> CM
0190: 50 3b 0d 0a 0d 0a 63 6c 61 73 73 20 54 72 65 65 P;....class Tree
01a0: 73 41 6e 61 6c 79 73 69 73 20 7b 20 70 75 62 6c sAnalysis { publ
01b0: 69 63 3a 0d 0a 09 74 79 70 65 64 65 66 20 69 6e ic:...typedef in
01c0: 74 20 45 49 44 3b 0d 0a 09 69 6e 74 20 4e 3b 0d t EID;...int N;.
01d0: 0a 09 6c 6f 6e 67 20 6c 6f 6e 67 20 74 72 65 65 ..long long tree
01e0: 53 69 6d 69 6c 61 72 69 74 79 28 76 65 63 74 6f Similarity(vecto
01f0: 72 20 3c 69 6e 74 3e 20 74 72 65 65 31 2c 20 76 r <int> tree1, v
0200: 65 63 74 6f 72 20 3c 69 6e 74 3e 20 74 72 65 65 ector <int> tree
0210: 32 29 0d 0a 09 7b 0d 0a 09 09 4e 20 3d 20 74 72 2)...{....N = tr
0220: 65 65 31 2e 73 69 7a 65 28 29 20 2b 20 31 3b 0d ee1.size() + 1;.
0230: 0a 09 09 76 65 63 74 6f 72 3c 76 65 63 74 6f 72 ...vector<vector
0240: 3c 70 61 69 72 3c 45 49 44 2c 69 6e 74 3e 3e 3e <pair<EID,int>>>
0250: 20 54 31 28 4e 29 3b 0d 0a 09 09 76 65 63 74 6f T1(N);....vecto
0260: 72 3c 76 65 63 74 6f 72 3c 69 6e 74 3e 3e 20 54 r<vector<int>> T
0270: 32 28 4e 29 3b 0d 0a 09 09 66 6f 72 28 69 6e 74 2(N);....for(int
0280: 20 76 3d 30 3b 20 76 3c 4e 2d 31 3b 20 2b 2b 76 v=0; v<N-1; ++v
0290: 29 20 7b 0d 0a 09 09 09 69 6e 74 20 75 20 3d 20 ) {.....int u =
02a0: 74 72 65 65 31 5b 76 5d 3b 0d 0a 09 09 09 54 31 tree1[v];.....T1
02b0: 5b 76 5d 2e 65 6d 70 6c 61 63 65 5f 62 61 63 6b [v].emplace_back
02c0: 28 76 2c 20 75 29 3b 0d 0a 09 09 09 54 31 5b 75 (v, u);.....T1[u
02d0: 5d 2e 65 6d 70 6c 61 63 65 5f 62 61 63 6b 28 76 ].emplace_back(v
02e0: 2b 4e 2c 20 76 29 3b 0d 0a 09 09 7d 0d 0a 09 09 +N, v);....}....
02f0: 66 6f 72 28 69 6e 74 20 76 3d 30 3b 20 76 3c 4e for(int v=0; v<N
0300: 2d 31 3b 20 2b 2b 76 29 20 7b 0d 0a 09 09 09 69 -1; ++v) {.....i
0310: 6e 74 20 75 20 3d 20 74 72 65 65 32 5b 76 5d 3b nt u = tree2[v];
0320: 0d 0a 09 09 09 54 32 5b 76 5d 2e 70 75 73 68 5f .....T2[v].push_
0330: 62 61 63 6b 28 75 29 3b 0d 0a 09 09 09 54 32 5b back(u);.....T2[
0340: 75 5d 2e 70 75 73 68 5f 62 61 63 6b 28 76 29 3b u].push_back(v);
0350: 0d 0a 09 09 7d 0d 0a 0d 0a 09 09 4c 4c 20 74 6f ....}......LL to
0360: 74 61 6c 20 3d 20 30 3b 0d 0a 09 09 66 6f 72 28 tal = 0;....for(
0370: 69 6e 74 20 76 32 3d 30 3b 20 76 32 3c 4e 2d 31 int v2=0; v2<N-1
0380: 3b 20 2b 2b 76 32 29 20 7b 0d 0a 09 09 09 69 6e ; ++v2) {.....in
0390: 74 20 75 32 20 3d 20 74 72 65 65 32 5b 76 32 5d t u2 = tree2[v2]
03a0: 3b 0d 0a 0d 0a 09 09 09 66 75 6e 63 74 69 6f 6e ;.......function
03b0: 3c 76 6f 69 64 28 69 6e 74 2c 69 6e 74 29 3e 20 <void(int,int)>
03c0: 72 65 63 3b 0d 0a 09 09 09 76 65 63 74 6f 72 3c rec;.....vector<
03d0: 62 6f 6f 6c 3e 20 73 75 62 5f 76 75 28 4e 29 2c bool> sub_vu(N),
03e0: 20 73 75 62 5f 75 76 28 4e 2c 20 74 72 75 65 29 sub_uv(N, true)
03f0: 3b 0d 0a 09 09 09 72 65 63 20 3d 20 5b 26 5d 28 ;.....rec = [&](
0400: 69 6e 74 20 61 2c 20 69 6e 74 20 62 29 20 7b 0d int a, int b) {.
0410: 0a 09 09 09 09 73 75 62 5f 76 75 5b 62 5d 20 3d .....sub_vu[b] =
0420: 20 74 72 75 65 3b 0d 0a 09 09 09 09 73 75 62 5f true;......sub_
0430: 75 76 5b 62 5d 20 3d 20 66 61 6c 73 65 3b 0d 0a uv[b] = false;..
0440: 09 09 09 09 66 6f 72 28 69 6e 74 20 63 3a 20 54 ....for(int c: T
0450: 32 5b 62 5d 29 20 69 66 28 63 21 3d 61 29 0d 0a 2[b]) if(c!=a)..
0460: 09 09 09 09 09 72 65 63 28 62 2c 63 29 3b 0d 0a .....rec(b,c);..
0470: 09 09 09 7d 3b 0d 0a 09 09 09 72 65 63 28 76 32 ...};.....rec(v2
0480: 2c 20 75 32 29 3b 0d 0a 0d 0a 09 09 09 76 65 63 , u2);.......vec
0490: 74 6f 72 3c 69 6e 74 3e 20 6d 65 6d 6f 5f 76 75 tor<int> memo_vu
04a0: 28 32 2a 4e 2c 20 2d 31 29 2c 20 6d 65 6d 6f 5f (2*N, -1), memo_
04b0: 75 76 28 32 2a 4e 2c 20 2d 31 29 3b 0d 0a 09 09 uv(2*N, -1);....
04c0: 09 66 6f 72 28 69 6e 74 20 76 31 3d 30 3b 20 76 .for(int v1=0; v
04d0: 31 3c 4e 2d 31 3b 20 2b 2b 76 31 29 20 7b 0d 0a 1<N-1; ++v1) {..
04e0: 09 09 09 09 69 6e 74 20 75 31 20 3d 20 74 72 65 ....int u1 = tre
04f0: 65 31 5b 76 31 5d 3b 0d 0a 09 09 09 09 69 6e 74 e1[v1];......int
0500: 20 73 31 20 3d 20 73 69 6d 28 54 31 2c 20 76 31 s1 = sim(T1, v1
0510: 2c 20 20 20 76 31 2c 20 75 31 2c 20 73 75 62 5f , v1, u1, sub_
0520: 76 75 2c 20 6d 65 6d 6f 5f 76 75 29 3b 0d 0a 09 vu, memo_vu);...
0530: 09 09 09 69 6e 74 20 73 32 20 3d 20 73 69 6d 28 ...int s2 = sim(
0540: 54 31 2c 20 76 31 2c 20 20 20 76 31 2c 20 75 31 T1, v1, v1, u1
0550: 2c 20 73 75 62 5f 75 76 2c 20 6d 65 6d 6f 5f 75 , sub_uv, memo_u
0560: 76 29 3b 0d 0a 09 09 09 09 69 6e 74 20 73 33 20 v);......int s3
0570: 3d 20 73 69 6d 28 54 31 2c 20 76 31 2b 4e 2c 20 = sim(T1, v1+N,
0580: 75 31 2c 20 76 31 2c 20 73 75 62 5f 76 75 2c 20 u1, v1, sub_vu,
0590: 6d 65 6d 6f 5f 76 75 29 3b 0d 0a 09 09 09 09 69 memo_vu);......i
05a0: 6e 74 20 73 20 3d 20 6d 61 78 28 6d 61 78 28 73 nt s = max(max(s
05b0: 31 2c 20 73 32 29 2c 20 6d 61 78 28 73 33 2c 20 1, s2), max(s3,
05c0: 4e 2d 73 31 2d 73 32 2d 73 33 29 29 3b 0d 0a 09 N-s1-s2-s3));...
05d0: 09 09 09 74 6f 74 61 6c 20 2b 3d 20 73 2a 73 3b ...total += s*s;
05e0: 0d 0a 09 09 09 7d 0d 0a 09 09 7d 0d 0a 09 09 72 .....}....}....r
05f0: 65 74 75 72 6e 20 74 6f 74 61 6c 3b 0d 0a 09 7d eturn total;...}
0600: 0d 0a 0d 0a 09 69 6e 74 20 73 69 6d 28 63 6f 6e .....int sim(con
0610: 73 74 20 76 65 63 74 6f 72 3c 76 65 63 74 6f 72 st vector<vector
0620: 3c 70 61 69 72 3c 45 49 44 2c 69 6e 74 3e 3e 3e <pair<EID,int>>>
0630: 26 20 54 31 2c 20 69 6e 74 20 45 2c 20 69 6e 74 & T1, int E, int
0640: 20 61 31 2c 20 69 6e 74 20 62 31 2c 20 76 65 63 a1, int b1, vec
0650: 74 6f 72 3c 62 6f 6f 6c 3e 26 20 73 75 62 2c 20 tor<bool>& sub,
0660: 76 65 63 74 6f 72 3c 69 6e 74 3e 26 20 6d 65 6d vector<int>& mem
0670: 6f 29 0d 0a 09 7b 0d 0a 09 09 69 66 28 6d 65 6d o)...{....if(mem
0680: 6f 5b 45 5d 3e 3d 30 29 0d 0a 09 09 09 72 65 74 o[E]>=0).....ret
0690: 75 72 6e 20 6d 65 6d 6f 5b 45 5d 3b 0d 0a 0d 0a urn memo[E];....
06a0: 09 09 69 6e 74 20 74 6f 74 61 6c 20 3d 20 73 75 ..int total = su
06b0: 62 5b 62 31 5d 3b 0d 0a 09 09 66 6f 72 28 70 61 b[b1];....for(pa
06c0: 69 72 3c 45 49 44 2c 69 6e 74 3e 20 69 63 3a 20 ir<EID,int> ic:
06d0: 54 31 5b 62 31 5d 29 20 7b 45 49 44 20 69 64 3d T1[b1]) {EID id=
06e0: 69 63 2e 66 69 72 73 74 3b 20 69 6e 74 20 63 31 ic.first; int c1
06f0: 3d 69 63 2e 73 65 63 6f 6e 64 3b 20 69 66 28 63 =ic.second; if(c
0700: 31 20 21 3d 20 61 31 29 20 7b 0d 0a 09 09 09 74 1 != a1) {.....t
0710: 6f 74 61 6c 20 2b 3d 20 73 69 6d 28 54 31 2c 20 otal += sim(T1,
0720: 69 64 2c 20 62 31 2c 20 63 31 2c 20 73 75 62 2c id, b1, c1, sub,
0730: 20 6d 65 6d 6f 29 3b 0d 0a 09 09 7d 7d 0d 0a 09 memo);....}}...
0740: 09 72 65 74 75 72 6e 20 6d 65 6d 6f 5b 45 5d 20 .return memo[E]
0750: 3d 20 74 6f 74 61 6c 3b 0d 0a 09 7d 0d 0a 7d 3b = total;...}..};
0760: 0d 0a 0d 0a 2f 2f 20 42 45 47 49 4e 20 43 55 54 ....// BEGIN CUT
0770: 20 48 45 52 45 0d 0a 23 69 6e 63 6c 75 64 65 20 HERE..#include
0780: 3c 63 74 69 6d 65 3e 0d 0a 64 6f 75 62 6c 65 20 <ctime>..double
0790: 73 74 61 72 74 5f 74 69 6d 65 3b 20 73 74 72 69 start_time; stri
07a0: 6e 67 20 74 69 6d 65 72 28 29 0d 0a 20 7b 20 6f ng timer().. { o
07b0: 73 74 72 69 6e 67 73 74 72 65 61 6d 20 6f 73 3b stringstream os;
07c0: 20 6f 73 20 3c 3c 20 22 20 28 22 20 3c 3c 20 69 os << " (" << i
07d0: 6e 74 28 28 63 6c 6f 63 6b 28 29 2d 73 74 61 72 nt((clock()-star
07e0: 74 5f 74 69 6d 65 29 2f 43 4c 4f 43 4b 53 5f 50 t_time)/CLOCKS_P
07f0: 45 52 5f 53 45 43 2a 31 30 30 30 29 20 3c 3c 20 ER_SEC*1000) <<
0800: 22 20 6d 73 65 63 29 22 3b 20 72 65 74 75 72 6e " msec)"; return
0810: 20 6f 73 2e 73 74 72 28 29 3b 20 7d 0d 0a 74 65 os.str(); }..te
0820: 6d 70 6c 61 74 65 3c 74 79 70 65 6e 61 6d 65 20 mplate<typename
0830: 54 3e 20 6f 73 74 72 65 61 6d 26 20 6f 70 65 72 T> ostream& oper
0840: 61 74 6f 72 3c 3c 28 6f 73 74 72 65 61 6d 26 20 ator<<(ostream&
0850: 6f 73 2c 20 63 6f 6e 73 74 20 76 65 63 74 6f 72 os, const vector
0860: 3c 54 3e 26 20 76 29 0d 0a 20 7b 20 6f 73 20 3c <T>& v).. { os <
0870: 3c 20 22 7b 20 22 3b 0d 0a 20 20 20 66 6f 72 28 < "{ ";.. for(
0880: 74 79 70 65 6e 61 6d 65 20 76 65 63 74 6f 72 3c typename vector<
0890: 54 3e 3a 3a 63 6f 6e 73 74 5f 69 74 65 72 61 74 T>::const_iterat
08a0: 6f 72 20 69 74 3d 76 2e 62 65 67 69 6e 28 29 3b or it=v.begin();
08b0: 20 69 74 21 3d 76 2e 65 6e 64 28 29 3b 20 2b 2b it!=v.end(); ++
08c0: 69 74 29 0d 0a 20 20 20 6f 73 20 3c 3c 20 27 5c it).. os << '\
08d0: 22 27 20 3c 3c 20 2a 69 74 20 3c 3c 20 27 5c 22 "' << *it << '\"
08e0: 27 20 3c 3c 20 28 69 74 2b 31 3d 3d 76 2e 65 6e ' << (it+1==v.en
08f0: 64 28 29 20 3f 20 22 22 20 3a 20 22 2c 20 22 29 d() ? "" : ", ")
0900: 3b 20 6f 73 20 3c 3c 20 22 20 7d 22 3b 20 72 65 ; os << " }"; re
0910: 74 75 72 6e 20 6f 73 3b 20 7d 0d 0a 76 6f 69 64 turn os; }..void
0920: 20 76 65 72 69 66 79 5f 63 61 73 65 28 63 6f 6e verify_case(con
0930: 73 74 20 6c 6f 6e 67 20 6c 6f 6e 67 26 20 45 78 st long long& Ex
0940: 70 65 63 74 65 64 2c 20 63 6f 6e 73 74 20 6c 6f pected, const lo
0950: 6e 67 20 6c 6f 6e 67 26 20 52 65 63 65 69 76 65 ng long& Receive
0960: 64 29 20 7b 0d 0a 20 62 6f 6f 6c 20 6f 6b 20 3d d) {.. bool ok =
0970: 20 28 45 78 70 65 63 74 65 64 20 3d 3d 20 52 65 (Expected == Re
0980: 63 65 69 76 65 64 29 3b 0d 0a 20 69 66 28 6f 6b ceived);.. if(ok
0990: 29 20 63 65 72 72 20 3c 3c 20 22 50 41 53 53 45 ) cerr << "PASSE
09a0: 44 22 20 3c 3c 20 74 69 6d 65 72 28 29 20 3c 3c D" << timer() <<
09b0: 20 65 6e 64 6c 3b 20 20 65 6c 73 65 20 7b 20 63 endl; else { c
09c0: 65 72 72 20 3c 3c 20 22 46 41 49 4c 45 44 22 20 err << "FAILED"
09d0: 3c 3c 20 74 69 6d 65 72 28 29 20 3c 3c 20 65 6e << timer() << en
09e0: 64 6c 3b 0d 0a 20 63 65 72 72 20 3c 3c 20 22 5c dl;.. cerr << "\
09f0: 74 6f 3a 20 5c 22 22 20 3c 3c 20 45 78 70 65 63 to: \"" << Expec
0a00: 74 65 64 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 65 ted << '\"' << e
0a10: 6e 64 6c 20 3c 3c 20 22 5c 74 78 3a 20 5c 22 22 ndl << "\tx: \""
0a20: 20 3c 3c 20 52 65 63 65 69 76 65 64 20 3c 3c 20 << Received <<
0a30: 27 5c 22 27 20 3c 3c 20 65 6e 64 6c 3b 20 7d 20 '\"' << endl; }
0a40: 7d 0d 0a 23 64 65 66 69 6e 65 20 43 41 53 45 28 }..#define CASE(
0a50: 4e 29 20 7b 63 65 72 72 20 3c 3c 20 22 54 65 73 N) {cerr << "Tes
0a60: 74 20 43 61 73 65 20 23 22 20 3c 3c 20 4e 20 3c t Case #" << N <
0a70: 3c 20 22 2e 2e 2e 22 20 3c 3c 20 66 6c 75 73 68 < "..." << flush
0a80: 3b 20 73 74 61 72 74 5f 74 69 6d 65 3d 63 6c 6f ; start_time=clo
0a90: 63 6b 28 29 3b 0d 0a 23 64 65 66 69 6e 65 20 45 ck();..#define E
0aa0: 4e 44 09 20 76 65 72 69 66 79 5f 63 61 73 65 28 ND. verify_case(
0ab0: 5f 2c 20 54 72 65 65 73 41 6e 61 6c 79 73 69 73 _, TreesAnalysis
0ac0: 28 29 2e 74 72 65 65 53 69 6d 69 6c 61 72 69 74 ().treeSimilarit
0ad0: 79 28 74 72 65 65 31 2c 20 74 72 65 65 32 29 29 y(tree1, tree2))
0ae0: 3b 7d 0d 0a 69 6e 74 20 6d 61 69 6e 28 29 7b 0d ;}..int main(){.
0af0: 0a 0d 0a 43 41 53 45 28 30 29 0d 0a 09 69 6e 74 ...CASE(0)...int
0b00: 20 74 72 65 65 31 5f 5b 5d 20 3d 20 7b 31 7d 3b tree1_[] = {1};
0b10: 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 ... vector <int
0b20: 3e 20 74 72 65 65 31 28 74 72 65 65 31 5f 2c 20 > tree1(tree1_,
0b30: 74 72 65 65 31 5f 2b 73 69 7a 65 6f 66 28 74 72 tree1_+sizeof(tr
0b40: 65 65 31 5f 29 2f 73 69 7a 65 6f 66 28 2a 74 72 ee1_)/sizeof(*tr
0b50: 65 65 31 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 74 ee1_)); ...int t
0b60: 72 65 65 32 5f 5b 5d 20 3d 20 7b 31 7d 3b 0d 0a ree2_[] = {1};..
0b70: 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 . vector <int>
0b80: 74 72 65 65 32 28 74 72 65 65 32 5f 2c 20 74 72 tree2(tree2_, tr
0b90: 65 65 32 5f 2b 73 69 7a 65 6f 66 28 74 72 65 65 ee2_+sizeof(tree
0ba0: 32 5f 29 2f 73 69 7a 65 6f 66 28 2a 74 72 65 65 2_)/sizeof(*tree
0bb0: 32 5f 29 29 3b 20 0d 0a 09 6c 6f 6e 67 20 6c 6f 2_)); ...long lo
0bc0: 6e 67 20 5f 20 3d 20 31 4c 4c 3b 20 0d 0a 45 4e ng _ = 1LL; ..EN
0bd0: 44 0d 0a 43 41 53 45 28 31 29 0d 0a 09 69 6e 74 D..CASE(1)...int
0be0: 20 74 72 65 65 31 5f 5b 5d 20 3d 20 7b 32 2c 20 tree1_[] = {2,
0bf0: 34 2c 20 31 2c 20 30 7d 3b 0d 0a 09 20 20 76 65 4, 1, 0};... ve
0c00: 63 74 6f 72 20 3c 69 6e 74 3e 20 74 72 65 65 31 ctor <int> tree1
0c10: 28 74 72 65 65 31 5f 2c 20 74 72 65 65 31 5f 2b (tree1_, tree1_+
0c20: 73 69 7a 65 6f 66 28 74 72 65 65 31 5f 29 2f 73 sizeof(tree1_)/s
0c30: 69 7a 65 6f 66 28 2a 74 72 65 65 31 5f 29 29 3b izeof(*tree1_));
0c40: 20 0d 0a 09 69 6e 74 20 74 72 65 65 32 5f 5b 5d ...int tree2_[]
0c50: 20 3d 20 7b 31 2c 20 34 2c 20 34 2c 20 34 7d 3b = {1, 4, 4, 4};
0c60: 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 ... vector <int
0c70: 3e 20 74 72 65 65 32 28 74 72 65 65 32 5f 2c 20 > tree2(tree2_,
0c80: 74 72 65 65 32 5f 2b 73 69 7a 65 6f 66 28 74 72 tree2_+sizeof(tr
0c90: 65 65 32 5f 29 2f 73 69 7a 65 6f 66 28 2a 74 72 ee2_)/sizeof(*tr
0ca0: 65 65 32 5f 29 29 3b 20 0d 0a 09 6c 6f 6e 67 20 ee2_)); ...long
0cb0: 6c 6f 6e 67 20 5f 20 3d 20 31 31 31 4c 4c 3b 20 long _ = 111LL;
0cc0: 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 32 29 0d 0a ..END..CASE(2)..
0cd0: 09 69 6e 74 20 74 72 65 65 31 5f 5b 5d 20 3d 20 .int tree1_[] =
0ce0: 7b 31 2c 20 32 2c 20 33 2c 20 34 7d 3b 0d 0a 09 {1, 2, 3, 4};...
0cf0: 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 74 vector <int> t
0d00: 72 65 65 31 28 74 72 65 65 31 5f 2c 20 74 72 65 ree1(tree1_, tre
0d10: 65 31 5f 2b 73 69 7a 65 6f 66 28 74 72 65 65 31 e1_+sizeof(tree1
0d20: 5f 29 2f 73 69 7a 65 6f 66 28 2a 74 72 65 65 31 _)/sizeof(*tree1
0d30: 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 74 72 65 65 _)); ...int tree
0d40: 32 5f 5b 5d 20 3d 20 7b 31 2c 20 32 2c 20 33 2c 2_[] = {1, 2, 3,
0d50: 20 34 7d 0d 0a 3b 0d 0a 09 20 20 76 65 63 74 6f 4}..;... vecto
0d60: 72 20 3c 69 6e 74 3e 20 74 72 65 65 32 28 74 72 r <int> tree2(tr
0d70: 65 65 32 5f 2c 20 74 72 65 65 32 5f 2b 73 69 7a ee2_, tree2_+siz
0d80: 65 6f 66 28 74 72 65 65 32 5f 29 2f 73 69 7a 65 eof(tree2_)/size
0d90: 6f 66 28 2a 74 72 65 65 32 5f 29 29 3b 20 0d 0a of(*tree2_)); ..
0da0: 09 6c 6f 6e 67 20 6c 6f 6e 67 20 5f 20 3d 20 31 .long long _ = 1
0db0: 32 38 4c 4c 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 28LL; ..END..CAS
0dc0: 45 28 33 29 0d 0a 09 69 6e 74 20 74 72 65 65 31 E(3)...int tree1
0dd0: 5f 5b 5d 20 3d 20 7b 32 2c 20 33 2c 20 34 2c 20 _[] = {2, 3, 4,
0de0: 34 2c 20 35 2c 20 38 2c 20 35 2c 20 36 2c 20 31 4, 5, 8, 5, 6, 1
0df0: 30 2c 20 38 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 0, 8};... vecto
0e00: 72 20 3c 69 6e 74 3e 20 74 72 65 65 31 28 74 72 r <int> tree1(tr
0e10: 65 65 31 5f 2c 20 74 72 65 65 31 5f 2b 73 69 7a ee1_, tree1_+siz
0e20: 65 6f 66 28 74 72 65 65 31 5f 29 2f 73 69 7a 65 eof(tree1_)/size
0e30: 6f 66 28 2a 74 72 65 65 31 5f 29 29 3b 20 0d 0a of(*tree1_)); ..
0e40: 09 69 6e 74 20 74 72 65 65 32 5f 5b 5d 20 3d 20 .int tree2_[] =
0e50: 7b 39 2c 20 30 2c 20 31 2c 20 30 2c 20 33 2c 20 {9, 0, 1, 0, 3,
0e60: 30 2c 20 35 2c 20 30 2c 20 37 2c 20 31 30 7d 3b 0, 5, 0, 7, 10};
0e70: 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 ... vector <int
0e80: 3e 20 74 72 65 65 32 28 74 72 65 65 32 5f 2c 20 > tree2(tree2_,
0e90: 74 72 65 65 32 5f 2b 73 69 7a 65 6f 66 28 74 72 tree2_+sizeof(tr
0ea0: 65 65 32 5f 29 2f 73 69 7a 65 6f 66 28 2a 74 72 ee2_)/sizeof(*tr
0eb0: 65 65 32 5f 29 29 3b 20 0d 0a 09 6c 6f 6e 67 20 ee2_)); ...long
0ec0: 6c 6f 6e 67 20 5f 20 3d 20 36 33 30 36 4c 4c 3b long _ = 6306LL;
0ed0: 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 34 29 0d ..END..CASE(4).
0ee0: 0a 09 69 6e 74 20 74 72 65 65 31 5f 5b 5d 20 3d ..int tree1_[] =
0ef0: 20 7b 32 32 32 2c 20 32 36 31 2c 20 31 36 37 2c {222, 261, 167,
0f00: 20 31 33 33 2c 20 31 37 34 2c 20 31 35 30 2c 20 133, 174, 150,
0f10: 31 36 35 2c 20 33 31 31 2c 20 32 30 38 2c 20 32 165, 311, 208, 2
0f20: 36 38 2c 20 31 31 31 2c 20 32 32 32 2c 20 31 35 68, 111, 222, 15
0f30: 34 2c 20 32 37 37 2c 20 32 38 32 2c 20 32 30 31 4, 277, 282, 201
0f40: 2c 20 34 36 2c 20 31 32 34 2c 20 31 39 34 2c 20 , 46, 124, 194,
0f50: 33 33 31 2c 20 34 2c 20 32 31 36 2c 20 31 31 31 331, 4, 216, 111
0f60: 2c 20 0d 0a 32 37 35 2c 20 37 32 2c 20 33 32 32 , ..275, 72, 322
0f70: 2c 20 31 33 37 2c 20 32 31 36 2c 20 32 34 31 2c , 137, 216, 241,
0f80: 20 34 38 2c 20 37 32 2c 20 31 30 31 2c 20 32 33 48, 72, 101, 23
0f90: 32 2c 20 31 36 35 2c 20 31 35 31 2c 20 32 36 33 2, 165, 151, 263
0fa0: 2c 20 31 33 39 2c 20 31 36 2c 20 31 32 32 2c 20 , 139, 16, 122,
0fb0: 31 34 30 2c 20 38 34 2c 20 31 33 35 2c 20 33 31 140, 84, 135, 31
0fc0: 34 2c 20 31 30 36 2c 20 33 30 39 2c 20 31 32 36 4, 106, 309, 126
0fd0: 2c 20 31 30 32 2c 20 0d 0a 31 35 31 2c 20 32 30 , 102, ..151, 20
0fe0: 38 2c 20 32 37 2c 20 32 34 32 2c 20 39 33 2c 20 8, 27, 242, 93,
0ff0: 38 33 2c 20 33 31 34 2c 20 31 33 36 2c 20 37 37 83, 314, 136, 77
1000: 2c 20 38 32 2c 20 32 31 35 2c 20 31 36 2c 20 32 , 82, 215, 16, 2
1010: 33 32 2c 20 32 38 36 2c 20 31 35 36 2c 20 32 39 32, 286, 156, 29
1020: 34 2c 20 33 38 2c 20 36 37 2c 20 32 30 34 2c 20 4, 38, 67, 204,
1030: 32 30 36 2c 20 31 33 37 2c 20 31 37 34 2c 20 32 206, 137, 174, 2
1040: 38 32 2c 20 31 38 38 2c 20 0d 0a 31 34 33 2c 20 82, 188, ..143,
1050: 38 34 2c 20 32 37 39 2c 20 32 33 36 2c 20 31 33 84, 279, 236, 13
1060: 36 2c 20 31 35 38 2c 20 31 30 2c 20 36 35 2c 20 6, 158, 10, 65,
1070: 33 33 32 2c 20 31 32 32 2c 20 34 34 2c 20 33 32 332, 122, 44, 32
1080: 39 2c 20 36 32 2c 20 31 37 34 2c 20 36 37 2c 20 9, 62, 174, 67,
1090: 31 30 32 2c 20 32 31 36 2c 20 32 34 35 2c 20 32 102, 216, 245, 2
10a0: 39 36 2c 20 32 38 37 2c 20 33 30 37 2c 20 39 33 96, 287, 307, 93
10b0: 2c 20 31 39 37 2c 20 31 36 39 2c 20 0d 0a 32 36 , 197, 169, ..26
10c0: 38 2c 20 32 36 36 2c 20 32 39 34 2c 20 31 35 37 8, 266, 294, 157
10d0: 2c 20 32 37 37 2c 20 39 35 2c 20 36 38 2c 20 32 , 277, 95, 68, 2
10e0: 31 34 2c 20 31 33 35 2c 20 32 31 31 2c 20 31 32 14, 135, 211, 12
10f0: 37 2c 20 38 32 2c 20 31 30 38 2c 20 32 31 32 2c 7, 82, 108, 212,
1100: 20 31 36 31 2c 20 32 34 33 2c 20 32 31 32 2c 20 161, 243, 212,
1110: 32 30 37 2c 20 31 31 39 2c 20 31 31 39 2c 20 31 207, 119, 119, 1
1120: 35 38 2c 20 39 37 2c 20 32 39 30 2c 20 32 31 2c 58, 97, 290, 21,
1130: 20 0d 0a 32 31 37 2c 20 32 33 30 2c 20 38 35 2c ..217, 230, 85,
1140: 20 31 37 31 2c 20 31 33 2c 20 31 33 38 2c 20 32 171, 13, 138, 2
1150: 39 34 2c 20 33 30 34 2c 20 32 30 34 2c 20 33 31 94, 304, 204, 31
1160: 38 2c 20 31 31 35 2c 20 37 30 2c 20 32 31 30 2c 8, 115, 70, 210,
1170: 20 31 39 35 2c 20 32 32 33 2c 20 33 37 2c 20 31 195, 223, 37, 1
1180: 36 34 2c 20 31 34 39 2c 20 33 2c 20 31 36 34 2c 64, 149, 3, 164,
1190: 20 33 32 38 2c 20 33 31 36 2c 20 31 30 38 2c 20 328, 316, 108,
11a0: 33 33 30 2c 20 0d 0a 34 38 2c 20 33 38 2c 20 33 330, ..48, 38, 3
11b0: 32 34 2c 20 32 32 32 2c 20 31 39 33 2c 20 35 30 24, 222, 193, 50
11c0: 2c 20 34 31 2c 20 31 38 34 2c 20 39 33 2c 20 31 , 41, 184, 93, 1
11d0: 34 38 2c 20 34 31 2c 20 31 35 31 2c 20 31 33 39 48, 41, 151, 139
11e0: 2c 20 31 30 36 2c 20 33 30 31 2c 20 32 36 34 2c , 106, 301, 264,
11f0: 20 38 30 2c 20 32 34 39 2c 20 31 31 30 2c 20 32 80, 249, 110, 2
1200: 34 34 2c 20 31 30 39 2c 20 32 31 32 2c 20 32 32 44, 109, 212, 22
1210: 33 2c 20 32 37 39 2c 20 0d 0a 33 33 30 2c 20 36 3, 279, ..330, 6
1220: 37 2c 20 32 37 2c 20 33 30 31 2c 20 31 36 35 2c 7, 27, 301, 165,
1230: 20 32 33 36 2c 20 31 39 34 2c 20 33 2c 20 31 35 236, 194, 3, 15
1240: 37 2c 20 31 2c 20 32 31 37 2c 20 33 31 31 2c 20 7, 1, 217, 311,
1250: 38 37 2c 20 31 30 35 2c 20 34 2c 20 32 38 36 2c 87, 105, 4, 286,
1260: 20 33 37 2c 20 36 2c 20 33 31 2c 20 31 31 31 2c 37, 6, 31, 111,
1270: 20 36 36 2c 20 32 33 30 2c 20 32 32 37 2c 20 32 66, 230, 227, 2
1280: 34 34 2c 20 33 32 32 2c 20 0d 0a 31 39 36 2c 20 44, 322, ..196,
1290: 36 35 2c 20 36 39 2c 20 33 30 35 2c 20 31 31 32 65, 69, 305, 112
12a0: 2c 20 31 33 33 2c 20 32 33 31 2c 20 36 38 2c 20 , 133, 231, 68,
12b0: 31 35 33 2c 20 32 30 36 2c 20 33 30 39 2c 20 32 153, 206, 309, 2
12c0: 34 38 2c 20 33 32 39 2c 20 35 38 2c 20 36 39 2c 48, 329, 58, 69,
12d0: 20 36 39 2c 20 33 32 38 2c 20 30 2c 20 32 39 2c 69, 328, 0, 29,
12e0: 20 32 33 33 2c 20 32 34 33 2c 20 33 30 35 2c 20 233, 243, 305,
12f0: 31 36 37 2c 20 38 30 2c 20 36 35 2c 20 0d 0a 31 167, 80, 65, ..1
1300: 39 34 2c 20 31 39 30 2c 20 31 37 39 2c 20 31 34 94, 190, 179, 14
1310: 32 2c 20 31 39 36 2c 20 33 32 34 2c 20 32 30 36 2, 196, 324, 206
1320: 2c 20 31 33 34 2c 20 35 30 2c 20 32 37 32 2c 20 , 134, 50, 272,
1330: 32 36 31 2c 20 31 30 2c 20 31 34 37 2c 20 33 32 261, 10, 147, 32
1340: 39 2c 20 33 32 32 2c 20 31 34 2c 20 31 34 32 2c 9, 322, 14, 142,
1350: 20 31 36 39 2c 20 32 31 2c 20 32 39 36 2c 20 32 169, 21, 296, 2
1360: 38 34 2c 20 32 34 31 2c 20 35 35 2c 20 33 30 34 84, 241, 55, 304
1370: 2c 20 0d 0a 31 35 30 2c 20 31 36 36 2c 20 32 33 , ..150, 166, 23
1380: 30 2c 20 31 36 37 2c 20 33 30 34 2c 20 38 37 2c 0, 167, 304, 87,
1390: 20 31 35 36 2c 20 31 35 36 2c 20 39 37 2c 20 32 156, 156, 97, 2
13a0: 37 34 2c 20 33 32 34 2c 20 31 39 36 2c 20 31 30 74, 324, 196, 10
13b0: 31 2c 20 38 32 2c 20 31 30 36 2c 20 32 36 30 2c 1, 82, 106, 260,
13c0: 20 32 34 32 2c 20 32 33 33 2c 20 32 30 37 2c 20 242, 233, 207,
13d0: 33 30 35 2c 20 31 30 2c 20 31 36 36 2c 20 35 33 305, 10, 166, 53
13e0: 2c 20 31 38 2c 20 0d 0a 31 35 34 2c 20 32 33 33 , 18, ..154, 233
13f0: 2c 20 32 31 37 2c 20 32 39 36 2c 20 32 36 33 2c , 217, 296, 263,
1400: 20 31 36 38 2c 20 31 33 38 2c 20 33 30 2c 20 31 168, 138, 30, 1
1410: 31 35 2c 20 31 33 35 2c 20 31 38 38 2c 20 39 38 15, 135, 188, 98
1420: 2c 20 33 30 39 2c 20 32 39 32 2c 20 32 30 34 2c , 309, 292, 204,
1430: 20 31 35 30 2c 20 32 31 30 2c 20 33 33 32 2c 20 150, 210, 332,
1440: 33 33 30 2c 20 31 36 36 2c 20 39 36 2c 20 37 30 330, 166, 96, 70
1450: 2c 20 32 34 2c 20 32 32 39 2c 20 0d 0a 32 31 35 , 24, 229, ..215
1460: 2c 20 32 30 31 2c 20 32 38 35 2c 20 34 30 2c 20 , 201, 285, 40,
1470: 32 38 37 2c 20 31 34 32 2c 20 36 38 2c 20 31 33 287, 142, 68, 13
1480: 33 2c 20 32 30 38 2c 20 32 36 38 2c 20 31 36 31 3, 208, 268, 161
1490: 2c 20 33 31 30 2c 20 34 31 2c 20 32 30 33 2c 20 , 310, 41, 203,
14a0: 37 33 2c 20 32 37 35 2c 20 31 38 34 2c 20 31 36 73, 275, 184, 16
14b0: 33 2c 20 32 32 37 2c 20 38 39 2c 20 31 31 30 2c 3, 227, 89, 110,
14c0: 20 33 32 38 2c 20 31 30 38 2c 20 31 31 32 2c 20 328, 108, 112,
14d0: 0d 0a 31 32 35 2c 20 31 36 34 2c 20 31 32 37 2c ..125, 164, 127,
14e0: 20 31 37 39 2c 20 32 36 37 2c 20 32 32 31 2c 20 179, 267, 221,
14f0: 34 39 2c 20 31 33 39 2c 20 31 2c 20 38 34 2c 20 49, 139, 1, 84,
1500: 31 33 36 2c 20 33 38 2c 20 36 2c 20 37 30 2c 20 136, 38, 6, 70,
1510: 32 34 36 2c 20 32 34 33 2c 20 33 2c 20 31 38 38 246, 243, 3, 188
1520: 2c 20 32 39 37 7d 3b 0d 0a 09 20 20 76 65 63 74 , 297};... vect
1530: 6f 72 20 3c 69 6e 74 3e 20 74 72 65 65 31 28 74 or <int> tree1(t
1540: 72 65 65 31 5f 2c 20 74 72 65 65 31 5f 2b 73 69 ree1_, tree1_+si
1550: 7a 65 6f 66 28 74 72 65 65 31 5f 29 2f 73 69 7a zeof(tree1_)/siz
1560: 65 6f 66 28 2a 74 72 65 65 31 5f 29 29 3b 20 0d eof(*tree1_)); .
1570: 0a 09 69 6e 74 20 74 72 65 65 32 5f 5b 5d 20 3d ..int tree2_[] =
1580: 20 7b 31 37 34 2c 20 32 36 32 2c 20 31 39 35 2c {174, 262, 195,
1590: 20 32 38 38 2c 20 31 35 37 2c 20 32 37 38 2c 20 288, 157, 278,
15a0: 33 36 2c 20 31 33 33 2c 20 32 33 30 2c 20 32 37 36, 133, 230, 27
15b0: 33 2c 20 32 32 32 2c 20 31 33 38 2c 20 39 37 2c 3, 222, 138, 97,
15c0: 20 32 33 2c 20 31 38 39 2c 20 31 34 31 2c 20 32 23, 189, 141, 2
15d0: 39 36 2c 20 35 35 2c 20 34 35 2c 20 33 30 31 2c 96, 55, 45, 301,
15e0: 20 38 31 2c 20 31 39 39 2c 20 31 38 38 2c 20 32 81, 199, 188, 2
15f0: 38 39 2c 20 0d 0a 31 38 37 2c 20 31 36 34 2c 20 89, ..187, 164,
1600: 31 31 33 2c 20 35 38 2c 20 31 33 38 2c 20 33 30 113, 58, 138, 30
1610: 30 2c 20 32 38 39 2c 20 32 38 32 2c 20 33 32 39 0, 289, 282, 329
1620: 2c 20 39 31 2c 20 31 33 30 2c 20 31 37 38 2c 20 , 91, 130, 178,
1630: 39 32 2c 20 31 34 33 2c 20 34 38 2c 20 38 31 2c 92, 143, 48, 81,
1640: 20 33 31 31 2c 20 31 33 33 2c 20 31 35 31 2c 20 311, 133, 151,
1650: 32 38 36 2c 20 31 37 31 2c 20 31 39 36 2c 20 31 286, 171, 196, 1
1660: 39 39 2c 20 38 30 2c 20 0d 0a 38 33 2c 20 31 32 99, 80, ..83, 12
1670: 31 2c 20 36 35 2c 20 31 35 31 2c 20 32 37 37 2c 1, 65, 151, 277,
1680: 20 31 33 36 2c 20 34 39 2c 20 31 31 31 2c 20 35 136, 49, 111, 5
1690: 38 2c 20 33 36 2c 20 32 35 39 2c 20 31 34 2c 20 8, 36, 259, 14,
16a0: 33 31 2c 20 39 2c 20 31 33 36 2c 20 31 38 31 2c 31, 9, 136, 181,
16b0: 20 31 32 32 2c 20 33 32 34 2c 20 32 34 39 2c 20 122, 324, 249,
16c0: 31 31 34 2c 20 39 2c 20 33 37 2c 20 32 35 39 2c 114, 9, 37, 259,
16d0: 20 32 34 32 2c 20 31 36 35 2c 20 0d 0a 31 37 34 242, 165, ..174
16e0: 2c 20 33 34 2c 20 33 36 2c 20 32 39 38 2c 20 39 , 34, 36, 298, 9
16f0: 32 2c 20 33 30 31 2c 20 32 33 37 2c 20 31 37 38 2, 301, 237, 178
1700: 2c 20 38 32 2c 20 36 35 2c 20 32 39 35 2c 20 31 , 82, 65, 295, 1
1710: 31 30 2c 20 33 31 31 2c 20 32 37 34 2c 20 32 33 10, 311, 274, 23
1720: 35 2c 20 36 38 2c 20 35 36 2c 20 32 35 39 2c 20 5, 68, 56, 259,
1730: 31 38 30 2c 20 31 39 35 2c 20 35 32 2c 20 31 31 180, 195, 52, 11
1740: 30 2c 20 36 38 2c 20 31 34 30 2c 20 37 31 2c 20 0, 68, 140, 71,
1750: 0d 0a 35 32 2c 20 32 39 36 2c 20 32 39 30 2c 20 ..52, 296, 290,
1760: 31 31 35 2c 20 32 31 33 2c 20 38 32 2c 20 32 30 115, 213, 82, 20
1770: 39 2c 20 32 30 39 2c 20 37 34 2c 20 31 37 38 2c 9, 209, 74, 178,
1780: 20 33 30 32 2c 20 31 33 31 2c 20 39 39 2c 20 32 302, 131, 99, 2
1790: 30 35 2c 20 32 39 36 2c 20 33 30 39 2c 20 32 38 05, 296, 309, 28
17a0: 38 2c 20 31 38 30 2c 20 33 32 39 2c 20 37 31 2c 8, 180, 329, 71,
17b0: 20 31 34 33 2c 20 35 38 2c 20 31 35 32 2c 20 32 143, 58, 152, 2
17c0: 37 33 2c 20 0d 0a 31 39 36 2c 20 37 2c 20 31 36 73, ..196, 7, 16
17d0: 39 2c 20 38 38 2c 20 32 33 31 2c 20 33 33 31 2c 9, 88, 231, 331,
17e0: 20 32 31 33 2c 20 31 38 31 2c 20 38 30 2c 20 32 213, 181, 80, 2
17f0: 34 39 2c 20 31 37 30 2c 20 32 34 36 2c 20 31 36 49, 170, 246, 16
1800: 2c 20 31 32 37 2c 20 37 35 2c 20 32 37 36 2c 20 , 127, 75, 276,
1810: 33 33 32 2c 20 31 37 34 2c 20 32 31 2c 20 31 38 332, 174, 21, 18
1820: 30 2c 20 31 36 33 2c 20 37 38 2c 20 32 34 32 2c 0, 163, 78, 242,
1830: 20 33 31 32 2c 20 0d 0a 32 39 35 2c 20 31 39 39 312, ..295, 199
1840: 2c 20 38 39 2c 20 31 34 32 2c 20 38 35 2c 20 31 , 89, 142, 85, 1
1850: 39 35 2c 20 31 31 35 2c 20 31 31 39 2c 20 39 35 95, 115, 119, 95
1860: 2c 20 39 34 2c 20 32 37 39 2c 20 32 39 30 2c 20 , 94, 279, 290,
1870: 33 2c 20 33 33 2c 20 39 33 2c 20 32 38 34 2c 20 3, 33, 93, 284,
1880: 32 30 2c 20 34 37 2c 20 34 37 2c 20 37 38 2c 20 20, 47, 47, 78,
1890: 33 33 31 2c 20 32 37 31 2c 20 31 31 33 2c 20 31 331, 271, 113, 1
18a0: 37 39 2c 20 32 34 39 2c 20 0d 0a 33 33 31 2c 20 79, 249, ..331,
18b0: 39 32 2c 20 33 32 34 2c 20 39 2c 20 37 31 2c 20 92, 324, 9, 71,
18c0: 32 33 32 2c 20 34 36 2c 20 32 38 2c 20 32 38 39 232, 46, 28, 289
18d0: 2c 20 38 30 2c 20 32 38 2c 20 38 30 2c 20 31 33 , 80, 28, 80, 13
18e0: 34 2c 20 32 30 2c 20 32 38 30 2c 20 32 37 37 2c 4, 20, 280, 277,
18f0: 20 34 38 2c 20 32 30 35 2c 20 31 30 37 2c 20 35 48, 205, 107, 5
1900: 32 2c 20 33 32 30 2c 20 34 2c 20 31 39 31 2c 20 2, 320, 4, 191,
1910: 31 36 30 2c 20 31 38 32 2c 20 0d 0a 31 38 39 2c 160, 182, ..189,
1920: 20 32 32 37 2c 20 32 39 35 2c 20 31 31 35 2c 20 227, 295, 115,
1930: 35 34 2c 20 31 39 35 2c 20 37 38 2c 20 32 39 32 54, 195, 78, 292
1940: 2c 20 31 38 39 2c 20 32 37 33 2c 20 33 30 31 2c , 189, 273, 301,
1950: 20 36 39 2c 20 33 30 35 2c 20 33 36 2c 20 32 32 69, 305, 36, 22
1960: 32 2c 20 31 36 37 2c 20 33 32 36 2c 20 31 30 36 2, 167, 326, 106
1970: 2c 20 34 38 2c 20 34 35 2c 20 37 34 2c 20 36 31 , 48, 45, 74, 61
1980: 2c 20 31 38 31 2c 20 33 31 31 2c 20 0d 0a 32 39 , 181, 311, ..29
1990: 32 2c 20 32 37 30 2c 20 32 30 31 2c 20 33 34 2c 2, 270, 201, 34,
19a0: 20 33 31 34 2c 20 32 31 38 2c 20 32 31 34 2c 20 314, 218, 214,
19b0: 39 32 2c 20 32 36 39 2c 20 31 38 2c 20 33 37 2c 92, 269, 18, 37,
19c0: 20 31 35 31 2c 20 31 34 32 2c 20 32 30 39 2c 20 151, 142, 209,
19d0: 31 31 2c 20 32 32 37 2c 20 33 32 37 2c 20 31 39 11, 227, 327, 19
19e0: 38 2c 20 32 38 2c 20 32 37 32 2c 20 31 35 32 2c 8, 28, 272, 152,
19f0: 20 32 32 2c 20 34 37 2c 20 31 34 33 2c 20 0d 0a 22, 47, 143, ..
1a00: 33 33 32 2c 20 32 35 33 2c 20 32 37 33 2c 20 33 332, 253, 273, 3
1a10: 35 2c 20 37 38 2c 20 31 33 30 2c 20 32 39 35 2c 5, 78, 130, 295,
1a20: 20 32 32 33 2c 20 31 38 31 2c 20 33 32 39 2c 20 223, 181, 329,
1a30: 31 38 2c 20 32 33 38 2c 20 33 30 30 2c 20 31 38 18, 238, 300, 18
1a40: 36 2c 20 32 37 34 2c 20 39 39 2c 20 33 30 30 2c 6, 274, 99, 300,
1a50: 20 33 32 32 2c 20 34 31 2c 20 31 38 35 2c 20 33 322, 41, 185, 3
1a60: 31 31 2c 20 32 38 38 2c 20 31 39 38 2c 20 32 2c 11, 288, 198, 2,
1a70: 20 0d 0a 33 37 2c 20 38 33 2c 20 32 33 38 2c 20 ..37, 83, 238,
1a80: 31 33 33 2c 20 31 32 32 2c 20 31 37 38 2c 20 31 133, 122, 178, 1
1a90: 30 37 2c 20 31 30 36 2c 20 36 36 2c 20 32 33 38 07, 106, 66, 238
1aa0: 2c 20 36 39 2c 20 39 30 2c 20 33 38 2c 20 31 30 , 69, 90, 38, 10
1ab0: 39 2c 20 32 34 36 2c 20 32 37 38 2c 20 32 38 38 9, 246, 278, 288
1ac0: 2c 20 32 35 30 2c 20 33 32 31 2c 20 32 36 39 2c , 250, 321, 269,
1ad0: 20 31 33 30 2c 20 32 38 2c 20 31 31 35 2c 20 31 130, 28, 115, 1
1ae0: 32 32 2c 20 0d 0a 33 33 2c 20 31 38 35 2c 20 32 22, ..33, 185, 2
1af0: 37 35 2c 20 39 39 2c 20 31 33 30 2c 20 39 39 2c 75, 99, 130, 99,
1b00: 20 31 35 32 2c 20 32 36 38 2c 20 31 33 33 2c 20 152, 268, 133,
1b10: 32 34 39 2c 20 31 38 30 2c 20 33 30 2c 20 32 31 249, 180, 30, 21
1b20: 30 2c 20 32 30 31 2c 20 33 32 34 2c 20 32 39 2c 0, 201, 324, 29,
1b30: 20 32 39 30 2c 20 31 34 33 2c 20 33 2c 20 32 36 290, 143, 3, 26
1b40: 39 2c 20 36 38 2c 20 31 30 36 2c 20 32 33 30 2c 9, 68, 106, 230,
1b50: 20 31 2c 20 0d 0a 32 36 39 2c 20 32 39 2c 20 31 1, ..269, 29, 1
1b60: 32 30 2c 20 32 35 39 2c 20 33 32 34 2c 20 33 32 20, 259, 324, 32
1b70: 38 2c 20 32 33 2c 20 32 34 33 2c 20 39 2c 20 36 8, 23, 243, 9, 6
1b80: 31 2c 20 31 34 2c 20 31 31 38 2c 20 31 39 39 2c 1, 14, 118, 199,
1b90: 20 31 34 36 2c 20 32 33 37 2c 20 31 34 7d 3b 0d 146, 237, 14};.
1ba0: 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e .. vector <int>
1bb0: 20 74 72 65 65 32 28 74 72 65 65 32 5f 2c 20 74 tree2(tree2_, t
1bc0: 72 65 65 32 5f 2b 73 69 7a 65 6f 66 28 74 72 65 ree2_+sizeof(tre
1bd0: 65 32 5f 29 2f 73 69 7a 65 6f 66 28 2a 74 72 65 e2_)/sizeof(*tre
1be0: 65 32 5f 29 29 3b 20 0d 0a 09 6c 6f 6e 67 20 6c e2_)); ...long l
1bf0: 6f 6e 67 20 5f 20 3d 20 31 31 34 37 38 36 34 38 ong _ = 11478648
1c00: 30 35 32 4c 4c 3b 20 0d 0a 45 4e 44 0d 0a 2f 2a 052LL; ..END../*
1c10: 0d 0a 43 41 53 45 28 35 29 0d 0a 09 69 6e 74 20 ..CASE(5)...int
1c20: 74 72 65 65 31 5f 5b 5d 20 3d 20 3b 0d 0a 09 20 tree1_[] = ;...
1c30: 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 74 72 vector <int> tr
1c40: 65 65 31 28 74 72 65 65 31 5f 2c 20 74 72 65 65 ee1(tree1_, tree
1c50: 31 5f 2b 73 69 7a 65 6f 66 28 74 72 65 65 31 5f 1_+sizeof(tree1_
1c60: 29 2f 73 69 7a 65 6f 66 28 2a 74 72 65 65 31 5f )/sizeof(*tree1_
1c70: 29 29 3b 20 0d 0a 09 69 6e 74 20 74 72 65 65 32 )); ...int tree2
1c80: 5f 5b 5d 20 3d 20 3b 0d 0a 09 20 20 76 65 63 74 _[] = ;... vect
1c90: 6f 72 20 3c 69 6e 74 3e 20 74 72 65 65 32 28 74 or <int> tree2(t
1ca0: 72 65 65 32 5f 2c 20 74 72 65 65 32 5f 2b 73 69 ree2_, tree2_+si
1cb0: 7a 65 6f 66 28 74 72 65 65 32 5f 29 2f 73 69 7a zeof(tree2_)/siz
1cc0: 65 6f 66 28 2a 74 72 65 65 32 5f 29 29 3b 20 0d eof(*tree2_)); .
1cd0: 0a 09 6c 6f 6e 67 20 6c 6f 6e 67 20 5f 20 3d 20 ..long long _ =
1ce0: 4c 4c 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 LL; ..END..CASE(
1cf0: 36 29 0d 0a 09 69 6e 74 20 74 72 65 65 31 5f 5b 6)...int tree1_[
1d00: 5d 20 3d 20 3b 0d 0a 09 20 20 76 65 63 74 6f 72 ] = ;... vector
1d10: 20 3c 69 6e 74 3e 20 74 72 65 65 31 28 74 72 65 <int> tree1(tre
1d20: 65 31 5f 2c 20 74 72 65 65 31 5f 2b 73 69 7a 65 e1_, tree1_+size
1d30: 6f 66 28 74 72 65 65 31 5f 29 2f 73 69 7a 65 6f of(tree1_)/sizeo
1d40: 66 28 2a 74 72 65 65 31 5f 29 29 3b 20 0d 0a 09 f(*tree1_)); ...
1d50: 69 6e 74 20 74 72 65 65 32 5f 5b 5d 20 3d 20 3b int tree2_[] = ;
1d60: 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 ... vector <int
1d70: 3e 20 74 72 65 65 32 28 74 72 65 65 32 5f 2c 20 > tree2(tree2_,
1d80: 74 72 65 65 32 5f 2b 73 69 7a 65 6f 66 28 74 72 tree2_+sizeof(tr
1d90: 65 65 32 5f 29 2f 73 69 7a 65 6f 66 28 2a 74 72 ee2_)/sizeof(*tr
1da0: 65 65 32 5f 29 29 3b 20 0d 0a 09 6c 6f 6e 67 20 ee2_)); ...long
1db0: 6c 6f 6e 67 20 5f 20 3d 20 4c 4c 3b 20 0d 0a 45 long _ = LL; ..E
1dc0: 4e 44 0d 0a 2a 2f 0d 0a 7d 0d 0a 2f 2f 20 45 4e ND..*/..}..// EN
1dd0: 44 20 43 55 54 20 48 45 52 45 0d 0a D CUT HERE..