#define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; const int INF = INT_MAX / 4; vector a; vector > edges; int solve(int curr, int prev, int prevValue, int& ans) { map maxValue; for(int next : edges[curr]){ if(next == prev || ((a[curr] < prevValue) ^ (a[curr] < a[next]))) continue; maxValue[a[next]] = max(maxValue[a[next]], solve(next, curr, a[curr], ans)); } int score = maxValue.size() * (maxValue.size() - 1) / 2; for(const auto& p : maxValue) score += p.second; ans = max(score, ans); maxValue[prevValue] = 0; score = maxValue.size() * (maxValue.size() - 1) / 2; for(const auto& p : maxValue) score += p.second; return score; } int main() { int n; cin >> n; a.resize(n); for(int i=0; i> a[i]; edges.assign(n, vector()); for(int i=0; i> x >> y; -- x; -- y; edges[x].push_back(y); edges[y].push_back(x); } int ans = 0; solve(0, -1, -INF, ans); ans, solve(0, -1, INF, ans); cout << ans << endl; return 0; }