#include <bits/stdc++.h> using namespace std; typedef long long i64; const int MAX_BUFFER = 1 << 20; char _read_buffer[MAX_BUFFER]; char* _read_ptr = _read_buffer; char* _read_end = _read_buffer; inline char read_char() { if (_read_ptr == _read_end) { _read_end = _read_buffer + fread(_read_buffer, 1, MAX_BUFFER, stdin); _read_ptr = _read_buffer; } return *_read_ptr ++; } inline int read_int() { int res = 0, neg = 0; char ch = read_char(); while (ch != '-' && (ch < '0' || ch > '9')) { ch = read_char(); } if (ch == '-') { neg = 1; ch = read_char(); } while ('0' <= ch && ch <= '9') { res = res * 10 + (ch - '0'); ch = read_char(); } return neg ? -res : res; } const int MAX_N = 100000 + 5; const i64 INF64 = 999999999999999999ll; int N, R; int a[MAX_N]; int ey[MAX_N << 1], enext[MAX_N << 1], elast[MAX_N]; int fath[MAX_N], size[MAX_N], depth[MAX_N]; int son[MAX_N], anc[MAX_N], des[MAX_N]; i64 ans[MAX_N]; void dfs_tcp_1(int u, int fa) { fath[u] = fa; size[u] = 1; depth[u] = depth[fa] + 1; for (int j = elast[u]; j; j = enext[j]) { int v = ey[j]; if (v != fa) { dfs_tcp_1(v, u); size[u] += size[v]; son[u] = size[v] > size[son[u]] ? v : son[u]; } } } void dfs_tcp_2(int u, int anc_) { anc[u] = anc_; des[u] = u; if (son[u]) { dfs_tcp_2(son[u], anc_); des[u] = des[son[u]]; } for (int j = elast[u]; j; j = enext[j]) { int v = ey[j]; if (v != fath[u] && v != son[u]) { dfs_tcp_2(v, v); } } } struct TreapNode { i64 t, max; int x, lazy; int up, son[2]; }; TreapNode node[MAX_N]; int tot_node; struct Treap { int root; int xL, xR; inline void update(int i) { i64 v0 = node[node[i].son[0]].max; i64 v1 = node[node[i].son[1]].max; i64 v = node[i].t - node[i].x; node[i].max = max(v, max(v0, v1)); } inline void push_down(int i) { int lz = node[i].lazy; node[i].lazy = 0; int s = node[i].son[0]; if (s) { node[s].x += lz; node[s].max -= lz; node[s].lazy += lz; } s = node[i].son[1]; if (s) { node[s].x += lz; node[s].max -= lz; node[s].lazy += lz; } } inline void rotate(int &i, int c) { int j = node[i].son[c]; node[i].son[c] = node[j].son[!c]; node[j].son[!c] = i; node[j].max = node[i].max; update(i); i = j; } void _insert_or_update(int &i, int k) { if (i == 0) { i = k; node[i].max = node[i].t - node[i].x; return; } if (node[i].lazy) { push_down(i); } if (node[i].x == node[k].x) { if (node[i].t < node[k].t) { node[i].t = node[k].t; update(i); } return; } int c = node[i].x < node[k].x; _insert_or_update(node[i].son[c], k); update(i); if (node[i].up < node[node[i].son[c]].up) { rotate(i, c); } } void insert_or_update(int k, i64 t, int x) { node[k].t = t; node[k].x = x; node[k].lazy = 0; node[k].son[0] = 0; node[k].son[1] = 0; node[k].up = rand() << 15 ^ rand(); _insert_or_update(root, k); } int _merge(int i, int j) { if (i == 0 || j == 0) { return i + j; } else if (node[i].up > node[j].up) { node[i].son[1] = _merge(node[i].son[1], j); update(i); return i; } else { node[j].son[0] = _merge(i, node[j].son[0]); update(j); return j; } } int _find_and_erase(int &i, int x) { if (i == 0) { return 0; } if (node[i].lazy) { push_down(i); } if (node[i].x == x) { int j = i; i = _merge(node[i].son[0], node[i].son[1]); return j; } int c = node[i].x < x; int j = _find_and_erase(node[i].son[c], x); update(i); return j; } int find_and_erase(int x) { return _find_and_erase(root, x); } void _modify(int i, int l, int r, int xl, int xr) { if (i == 0) { return; } else if (xl <= l && r <= xr) { node[i].x -= 1; node[i].max += 1; node[i].lazy -= 1; return; } if (node[i].lazy) { push_down(i); } if (xl <= node[i].x && node[i].x <= xr) { node[i].x -= 1; } if (node[i].son[0] && xl < node[i].x) { _modify(node[i].son[0], l, node[i].x - 1, xl, xr); } if (node[i].son[1] && node[i].x < xr) { _modify(node[i].son[1], node[i].x + 1, r, xl, xr); } update(i); } void modify(int xl, int xr) { _modify(root, xL, xR, xl, xr); } i64 _query(int i, int l, int r, int xl, int xr) { i64 res = -INF64; if (i == 0) { return -INF64; } else if (xl <= l && r <= xr) { return node[i].max; } if (node[i].lazy) { push_down(i); } if (xl <= node[i].x && node[i].x <= xr) { res = node[i].t - node[i].x; } if (node[i].son[0] && xl < node[i].x) { res = max(res, _query(node[i].son[0], l, node[i].x - 1, xl, xr)); } if (node[i].son[1] && node[i].x < xr) { res = max(res, _query(node[i].son[1], node[i].x + 1, r, xl, xr)); } return res; } i64 query(int xl, int xr) { return _query(root, xL, xR, xl, xr); } }; Treap tr[MAX_N]; i64 tcp_query(int u) { i64 res = -INF64; while (u) { int v = anc[u]; i64 tmp = tr[v].query(depth[v], depth[u]); res = res < tmp ? tmp : res; u = fath[v]; } return res; } void tcp_modify(int u) { int i = 0; while (u) { int v = anc[u]; int j = tr[v].find_and_erase(depth[v]); tr[v].modify(depth[v], depth[u]); if (i) { tr[v].insert_or_update(i, node[i].t, node[i].x - 1); } i = j; u = fath[v]; } if (i) { tr[R].insert_or_update(i, node[i].t + 1, node[i].x); } } int main() { N = read_int(); R = read_int(); for (int i = 1; i <= N; i ++) { a[i] = read_int(); } for (int i = 1, j = 1; i < N; i ++) { int x = read_int(); int y = read_int(); ey[j] = y; enext[j] = elast[x]; elast[x] = j ++; ey[j] = x; enext[j] = elast[y]; elast[y] = j ++; } dfs_tcp_1(R, 0); dfs_tcp_2(R, R); for (int i = 1; i <= N; i ++) { if (anc[i] == i) { tr[i].xL = depth[i]; tr[i].xR = depth[des[i]]; } } tr[R].insert_or_update(N + 1, 1, depth[R]); i64 answer = 0; for (int i = 1; i <= N; i ++) { ans[i] = tcp_query(i) + depth[i] + a[i]; tcp_modify(i); tr[anc[i]].insert_or_update(i, ans[i] + 1, depth[i]); answer = answer < ans[i] ? ans[i] : answer; } printf("%lld\n", answer); return 0; }