#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <tuple>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
class TreesAnalysis { public:
typedef int EID;
int N;
long long treeSimilarity(vector <int> tree1, vector <int> tree2)
{
N = tree1.size() + 1;
vector<vector<pair<EID,int>>> T1(N);
vector<vector<int>> T2(N);
for(int v=0; v<N-1; ++v) {
int u = tree1[v];
T1[v].emplace_back(v, u);
T1[u].emplace_back(v+N, v);
}
for(int v=0; v<N-1; ++v) {
int u = tree2[v];
T2[v].push_back(u);
T2[u].push_back(v);
}
LL total = 0;
for(int v2=0; v2<N-1; ++v2) {
int u2 = tree2[v2];
function<void(int,int)> rec;
vector<bool> sub_vu(N), sub_uv(N, true);
rec = [&](int a, int b) {
sub_vu[b] = true;
sub_uv[b] = false;
for(int c: T2[b]) if(c!=a)
rec(b,c);
};
rec(v2, u2);
vector<int> memo_vu(2*N, -1), memo_uv(2*N, -1);
for(int v1=0; v1<N-1; ++v1) {
int u1 = tree1[v1];
int s1 = sim(T1, v1, v1, u1, sub_vu, memo_vu);
int s2 = sim(T1, v1, v1, u1, sub_uv, memo_uv);
int s3 = sim(T1, v1+N, u1, v1, sub_vu, memo_vu);
int s = max(max(s1, s2), max(s3, N-s1-s2-s3));
total += s*s;
}
}
return total;
}
int sim(const vector<vector<pair<EID,int>>>& T1, int E, int a1, int b1, vector<bool>& sub, vector<int>& memo)
{
if(memo[E]>=0)
return memo[E];
int total = sub[b1];
for(pair<EID,int> ic: T1[b1]) {EID id=ic.first; int c1=ic.second; if(c1 != a1) {
total += sim(T1, id, b1, c1, sub, memo);
}}
return memo[E] = total;
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const long long& Expected, const long long& Received) {
bool ok = (Expected == Received);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, TreesAnalysis().treeSimilarity(tree1, tree2));}
int main(){
CASE(0)
int tree1_[] = {1};
vector <int> tree1(tree1_, tree1_+sizeof(tree1_)/sizeof(*tree1_));
int tree2_[] = {1};
vector <int> tree2(tree2_, tree2_+sizeof(tree2_)/sizeof(*tree2_));
long long _ = 1LL;
END
CASE(1)
int tree1_[] = {2, 4, 1, 0};
vector <int> tree1(tree1_, tree1_+sizeof(tree1_)/sizeof(*tree1_));
int tree2_[] = {1, 4, 4, 4};
vector <int> tree2(tree2_, tree2_+sizeof(tree2_)/sizeof(*tree2_));
long long _ = 111LL;
END
CASE(2)
int tree1_[] = {1, 2, 3, 4};
vector <int> tree1(tree1_, tree1_+sizeof(tree1_)/sizeof(*tree1_));
int tree2_[] = {1, 2, 3, 4}
;
vector <int> tree2(tree2_, tree2_+sizeof(tree2_)/sizeof(*tree2_));
long long _ = 128LL;
END
CASE(3)
int tree1_[] = {2, 3, 4, 4, 5, 8, 5, 6, 10, 8};
vector <int> tree1(tree1_, tree1_+sizeof(tree1_)/sizeof(*tree1_));
int tree2_[] = {9, 0, 1, 0, 3, 0, 5, 0, 7, 10};
vector <int> tree2(tree2_, tree2_+sizeof(tree2_)/sizeof(*tree2_));
long long _ = 6306LL;
END
CASE(4)
int tree1_[] = {222, 261, 167, 133, 174, 150, 165, 311, 208, 268, 111, 222, 154, 277, 282, 201, 46, 124, 194, 331, 4, 216, 111,
275, 72, 322, 137, 216, 241, 48, 72, 101, 232, 165, 151, 263, 139, 16, 122, 140, 84, 135, 314, 106, 309, 126, 102,
151, 208, 27, 242, 93, 83, 314, 136, 77, 82, 215, 16, 232, 286, 156, 294, 38, 67, 204, 206, 137, 174, 282, 188,
143, 84, 279, 236, 136, 158, 10, 65, 332, 122, 44, 329, 62, 174, 67, 102, 216, 245, 296, 287, 307, 93, 197, 169,
268, 266, 294, 157, 277, 95, 68, 214, 135, 211, 127, 82, 108, 212, 161, 243, 212, 207, 119, 119, 158, 97, 290, 21,
217, 230, 85, 171, 13, 138, 294, 304, 204, 318, 115, 70, 210, 195, 223, 37, 164, 149, 3, 164, 328, 316, 108, 330,
48, 38, 324, 222, 193, 50, 41, 184, 93, 148, 41, 151, 139, 106, 301, 264, 80, 249, 110, 244, 109, 212, 223, 279,
330, 67, 27, 301, 165, 236, 194, 3, 157, 1, 217, 311, 87, 105, 4, 286, 37, 6, 31, 111, 66, 230, 227, 244, 322,
196, 65, 69, 305, 112, 133, 231, 68, 153, 206, 309, 248, 329, 58, 69, 69, 328, 0, 29, 233, 243, 305, 167, 80, 65,
194, 190, 179, 142, 196, 324, 206, 134, 50, 272, 261, 10, 147, 329, 322, 14, 142, 169, 21, 296, 284, 241, 55, 304,
150, 166, 230, 167, 304, 87, 156, 156, 97, 274, 324, 196, 101, 82, 106, 260, 242, 233, 207, 305, 10, 166, 53, 18,
154, 233, 217, 296, 263, 168, 138, 30, 115, 135, 188, 98, 309, 292, 204, 150, 210, 332, 330, 166, 96, 70, 24, 229,
215, 201, 285, 40, 287, 142, 68, 133, 208, 268, 161, 310, 41, 203, 73, 275, 184, 163, 227, 89, 110, 328, 108, 112,
125, 164, 127, 179, 267, 221, 49, 139, 1, 84, 136, 38, 6, 70, 246, 243, 3, 188, 297};
vector <int> tree1(tree1_, tree1_+sizeof(tree1_)/sizeof(*tree1_));
int tree2_[] = {174, 262, 195, 288, 157, 278, 36, 133, 230, 273, 222, 138, 97, 23, 189, 141, 296, 55, 45, 301, 81, 199, 188, 289,
187, 164, 113, 58, 138, 300, 289, 282, 329, 91, 130, 178, 92, 143, 48, 81, 311, 133, 151, 286, 171, 196, 199, 80,
83, 121, 65, 151, 277, 136, 49, 111, 58, 36, 259, 14, 31, 9, 136, 181, 122, 324, 249, 114, 9, 37, 259, 242, 165,
174, 34, 36, 298, 92, 301, 237, 178, 82, 65, 295, 110, 311, 274, 235, 68, 56, 259, 180, 195, 52, 110, 68, 140, 71,
52, 296, 290, 115, 213, 82, 209, 209, 74, 178, 302, 131, 99, 205, 296, 309, 288, 180, 329, 71, 143, 58, 152, 273,
196, 7, 169, 88, 231, 331, 213, 181, 80, 249, 170, 246, 16, 127, 75, 276, 332, 174, 21, 180, 163, 78, 242, 312,
295, 199, 89, 142, 85, 195, 115, 119, 95, 94, 279, 290, 3, 33, 93, 284, 20, 47, 47, 78, 331, 271, 113, 179, 249,
331, 92, 324, 9, 71, 232, 46, 28, 289, 80, 28, 80, 134, 20, 280, 277, 48, 205, 107, 52, 320, 4, 191, 160, 182,
189, 227, 295, 115, 54, 195, 78, 292, 189, 273, 301, 69, 305, 36, 222, 167, 326, 106, 48, 45, 74, 61, 181, 311,
292, 270, 201, 34, 314, 218, 214, 92, 269, 18, 37, 151, 142, 209, 11, 227, 327, 198, 28, 272, 152, 22, 47, 143,
332, 253, 273, 35, 78, 130, 295, 223, 181, 329, 18, 238, 300, 186, 274, 99, 300, 322, 41, 185, 311, 288, 198, 2,
37, 83, 238, 133, 122, 178, 107, 106, 66, 238, 69, 90, 38, 109, 246, 278, 288, 250, 321, 269, 130, 28, 115, 122,
33, 185, 275, 99, 130, 99, 152, 268, 133, 249, 180, 30, 210, 201, 324, 29, 290, 143, 3, 269, 68, 106, 230, 1,
269, 29, 120, 259, 324, 328, 23, 243, 9, 61, 14, 118, 199, 146, 237, 14};
vector <int> tree2(tree2_, tree2_+sizeof(tree2_)/sizeof(*tree2_));
long long _ = 11478648052LL;
END
/*
CASE(5)
int tree1_[] = ;
vector <int> tree1(tree1_, tree1_+sizeof(tree1_)/sizeof(*tree1_));
int tree2_[] = ;
vector <int> tree2(tree2_, tree2_+sizeof(tree2_)/sizeof(*tree2_));
long long _ = LL;
END
CASE(6)
int tree1_[] = ;
vector <int> tree1(tree1_, tree1_+sizeof(tree1_)/sizeof(*tree1_));
int tree2_[] = ;
vector <int> tree2(tree2_, tree2_+sizeof(tree2_)/sizeof(*tree2_));
long long _ = LL;
END
*/
}
// END CUT HERE