import java.io.BufferedInputStream; import java.io.IOException; import java.io.PrintWriter; import java.util.*; import java.util.function.IntUnaryOperator; import java.util.function.LongUnaryOperator; import java.util.stream.Collectors; import java.util.stream.IntStream; import static java.lang.Math.max; import static java.lang.Math.min; public class Main { static In in = new In(); static Out out = new Out(false, false); static final long inf = 0x1fffffffffffffffL; static final int iinf = 0x3fffffff; static final double eps = 1e-9; static long mod = 998244353; int[] a; int[] ans; void solve() { int n = in.nextInt(); a = in.nextIntArray(n); ans = new int[n]; List> edges = in.nextGraph(n, n - 1, false); new CentroidDecomposition2(edges) { void query(int center, List> left, List> right) { f(center, left, right); f(center, right, left); } }; out.println(ans); } List table; void f(int s, List> x, List> y) { table = new ArrayList<>(); dfs1(s, s, 0, x); for (int i = table.size() - 2; i >= 0; i--) { table.set(i, min(table.get(i), table.get(i + 1))); } dfs2(s, s, 0, y); } void dfs1(int node, int parent, int depth, List> x) { while (table.size() <= depth) { table.add(0); } table.set(depth, min(table.get(depth), -a[node])); for (int child : x.get(node)) { if (child == parent) continue; dfs1(child, node, depth + 1, x); } } void dfs2(int node, int parent, int depth, List> y) { int left = -1; int right = table.size(); while (right - left > 1) { int mid = (left + right) / 2; if (table.get(mid) <= -a[node]) { left = mid; } else { right = mid; } } if (right >= 1) { ans[node] = max(ans[node], depth + right - 1); } for (int child : y.get(node)) { if (child == parent) continue; dfs2(child, node, depth + 1, y); } } public static void main(String... args) { new Main().solve(); out.flush(); } } abstract class CentroidDecomposition { int[] size; int[] count; int[] sort; boolean[] xy; int center; int n; List>> bufLeft = new ArrayList<>(); List>> bufRight = new ArrayList<>(); abstract void query(int center, List> left, List> right); public CentroidDecomposition(List> edges) { this.n = edges.size(); this.size = new int[n]; this.count = new int[n]; this.sort = new int[n]; this.xy = new boolean[n]; rec(edges.size(), 0, edges, 0); } private void rec(int m, int root, List> edges, int depth) { if (m <= 2) { return; } center = -1; size(root, -1, m, edges); int s = center; int max = 0; for (int nei : edges.get(s)) { if (size[nei] > size[s]) { size[nei] = m - size[s]; } count[size[nei]]++; max = max(max, size[nei] + 1); } for (int i = 1; i < max; i++) { count[i] += count[i - 1]; } for (int nei : edges.get(s)) { sort[--count[size[nei]]] = nei; } Arrays.fill(count, 0, max, 0); int xs = 0; int ys = 0; int g = edges.get(s).size(); for (int i = g - 1; i >= 0; i--) { if (xs < ys) { xy[sort[i]] = false; xs += size[sort[i]]; } else { xy[sort[i]] = true; ys += size[sort[i]]; } } while (bufLeft.size() <= depth) { List> edgesLeft = new ArrayList<>(); List> edgesRight = new ArrayList<>(); for (int i = 0; i < n; i++) { edgesLeft.add(new ArrayList<>()); edgesRight.add(new ArrayList<>()); } bufLeft.add(edgesLeft); bufRight.add(edgesRight); } List> left = bufLeft.get(depth); List> right = bufRight.get(depth); left.set(s, new ArrayList<>()); right.set(s, new ArrayList<>()); for (int nei : edges.get(s)) { if (xy[nei]) { right.get(s).add(nei); build(nei, s, edges, right); } else { left.get(s).add(nei); build(nei, s, edges, left); } } query(s, left, right); rec(xs + 1, s, left, depth + 1); rec(ys + 1, s, right, depth + 1); } private void build(int node, int parent, List> edges, List> sub) { sub.set(node, edges.get(node)); for (int child : edges.get(node)) { if (child != parent) { build(child, node, edges, sub); } } } private void size(int node, int parent, int m, List> edges) { size[node] = 1; int max = 0; for (int child : edges.get(node)) { if (child != parent) { size(child, node, m, edges); size[node] += size[child]; max = max(max, size[child]); } } max = max(max, m - size[node]); if (max * 2 <= m) { center = node; } } } abstract class CentroidDecomposition2 { int[] size; int[] count; int[] sort; int[] parent; boolean[] xy; int n; List>> bufLeft = new ArrayList<>(); List>> bufRight = new ArrayList<>(); abstract void query(int center, List> left, List> right); public CentroidDecomposition2(List> edges) { this.n = edges.size(); this.size = new int[n]; this.count = new int[n]; this.sort = new int[n]; this.xy = new boolean[n]; this.parent = new int[n]; rec(edges.size(), 0, edges, 0); } private void rec(int m, int root, List> edges, int depth) { if (m <= 2) { return; } int s = size(root, -1, m, edges); int max = 0; for (int nei : edges.get(s)) { if (size[nei] > size[s]) { size[nei] = m - size[s]; } count[size[nei]]++; max = max(max, size[nei] + 1); } for (int i = 1; i < max; i++) { count[i] += count[i - 1]; } for (int nei : edges.get(s)) { sort[--count[size[nei]]] = nei; } Arrays.fill(count, 0, max, 0); int xs = 0; int ys = 0; int g = edges.get(s).size(); for (int i = g - 1; i >= 0; i--) { if (xs < ys) { xy[sort[i]] = false; xs += size[sort[i]]; } else { xy[sort[i]] = true; ys += size[sort[i]]; } } while (bufLeft.size() <= depth) { List> edgesLeft = new ArrayList<>(); List> edgesRight = new ArrayList<>(); for (int i = 0; i < n; i++) { edgesLeft.add(null); edgesRight.add(null); } bufLeft.add(edgesLeft); bufRight.add(edgesRight); } List> left = bufLeft.get(depth); List> right = bufRight.get(depth); left.set(s, new ArrayList<>()); right.set(s, new ArrayList<>()); for (int nei : edges.get(s)) { if (xy[nei]) { right.get(s).add(nei); build(nei, s, edges, right); } else { left.get(s).add(nei); build(nei, s, edges, left); } } query(s, left, right); rec(xs + 1, s, left, depth + 1); rec(ys + 1, s, right, depth + 1); } private void build(int root, int par, List> edges, List> sub) { deque.addLast(root); parent[root] = par; while (!deque.isEmpty()) { int u = deque.removeLast(); sub.set(u, edges.get(u)); for (int child : edges.get(u)) { if (child != parent[u]) { parent[child] = u; deque.addLast(child); } } } } Deque deque = new ArrayDeque<>(); private int size(int root, int par, int m, List> edges) { int s = -1; deque.addLast(~root); deque.addLast(root); parent[root] = par; size[root] = 1; while (!deque.isEmpty()) { int u = deque.removeLast(); if (u < 0) { u = ~u; if (parent[u] != -1) { size[parent[u]] += size[u]; } int max = 0; for (int child : edges.get(u)) { if (child != parent[u]) { max = max(max, size[child]); } } max = max(max, m - size[u]); if (max * 2 <= m) { s = u; } } else { for (int child : edges.get(u)) { if (child != parent[u]) { parent[child] = u; size[child] = 1; deque.addLast(~child); deque.addLast(child); } } } } return s; } } class In { private final BufferedInputStream reader = new BufferedInputStream(System.in); private final byte[] buffer = new byte[0x10000]; private int i = 0; private int length = 0; public int read() { if (i == length) { i = 0; try { length = reader.read(buffer); } catch (IOException ignored) { } if (length == -1) { return 0; } } if (length <= i) { throw new RuntimeException(); } return buffer[i++]; } public String next() { StringBuilder builder = new StringBuilder(); int b = read(); while (b < '!' || '~' < b) { b = read(); } while ('!' <= b && b <= '~') { builder.appendCodePoint(b); b = read(); } return builder.toString(); } public String nextLine() { StringBuilder builder = new StringBuilder(); int b = read(); while (b != 0 && b != '\r' && b != '\n') { builder.appendCodePoint(b); b = read(); } if (b == '\r') { read(); } return builder.toString(); } public int nextInt() { long val = nextLong(); if (val < Integer.MIN_VALUE || Integer.MAX_VALUE < val) { throw new NumberFormatException(); } return (int)val; } public long nextLong() { int b = read(); while (b < '!' || '~' < b) { b = read(); } boolean neg = false; if (b == '-') { neg = true; b = read(); } long n = 0; int c = 0; while ('0' <= b && b <= '9') { n = n * 10 + b - '0'; b = read(); c++; } if (c == 0 || c >= 2 && n == 0) { throw new NumberFormatException(); } return neg ? -n : n; } public double nextDouble() { return Double.parseDouble(next()); } public char[] nextCharArray() { return next().toCharArray(); } public String[] nextStringArray(int n) { String[] s = new String[n]; for (int i = 0; i < n; i++) { s[i] = next(); } return s; } public char[][] nextCharMatrix(int n, int m) { char[][] a = new char[n][m]; for (int i = 0; i < n; i++) { a[i] = next().toCharArray(); } return a; } public int[] nextIntArray(int n) { int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = nextInt(); } return a; } public int[] nextIntArray(int n, IntUnaryOperator op) { int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = op.applyAsInt(nextInt()); } return a; } public int[][] nextIntMatrix(int h, int w) { int[][] a = new int[h][w]; for (int i = 0; i < h; i++) { a[i] = nextIntArray(w); } return a; } public long[] nextLongArray(int n) { long[] a = new long[n]; for (int i = 0; i < n; i++) { a[i] = nextLong(); } return a; } public long[] nextLongArray(int n, LongUnaryOperator op) { long[] a = new long[n]; for (int i = 0; i < n; i++) { a[i] = op.applyAsLong(nextLong()); } return a; } public long[][] nextLongMatrix(int h, int w) { long[][] a = new long[h][w]; for (int i = 0; i < h; i++) { a[i] = nextLongArray(w); } return a; } public List> nextGraph(int n, int m, boolean directed) { List> res = new ArrayList<>(); for (int i = 0; i < n; i++) { res.add(new ArrayList<>()); } for (int i = 0; i < m; i++) { int u = nextInt() - 1; int v = nextInt() - 1; res.get(u).add(v); if (!directed) { res.get(v).add(u); } } return res; } } class Out { private final PrintWriter out = new PrintWriter(System.out); private final PrintWriter err = new PrintWriter(System.err); public boolean autoFlush; public boolean enableDebug; public Out(boolean autoFlush, boolean enableDebug) { this.autoFlush = autoFlush; this.enableDebug = enableDebug; } public void debug(Object... args) { if (!enableDebug) { return; } if (args == null || args.getClass() != Object[].class) { args = new Object[] {args}; } err.println(Arrays.stream(args).map(obj -> format(obj, true)).collect(Collectors.joining(" "))); err.flush(); } private String format(Object obj, boolean canMultiline) { if (obj == null) return "null"; Class clazz = obj.getClass(); if (clazz == Double.class) return String.format("%.10f", obj); if (clazz == int[].class) return Arrays.toString((int[])obj); if (clazz == long[].class) return Arrays.toString((long[])obj); if (clazz == char[].class) return String.valueOf((char[])obj); if (clazz == boolean[].class) return IntStream.range(0, ((boolean[])obj).length).mapToObj(i -> ((boolean[])obj)[i] ? "1" : "0").collect(Collectors.joining()); if (clazz == double[].class) return Arrays.toString(Arrays.stream((double[])obj).mapToObj(a -> format(a, false)).toArray()); if (canMultiline && clazz.isArray() && clazz.componentType().isArray()) return Arrays.stream((Object[])obj).map(a -> format(a, false)).collect(Collectors.joining("\n")); if (clazz == Object[].class) return Arrays.toString(Arrays.stream((Object[])obj).map(a -> format(a, false)).toArray()); if (clazz.isArray()) return Arrays.toString((Object[])obj); return String.valueOf(obj); } public void println(Object... args) { if (args == null || args.getClass() != Object[].class) { args = new Object[] {args}; } out.println(Arrays.stream(args) .map(obj -> obj instanceof Double ? String.format("%.10f", obj) : String.valueOf(obj)) .collect(Collectors.joining(" "))); if (autoFlush) { out.flush(); } } public void println(char a) { out.println(a); if (autoFlush) { out.flush(); } } public void println(int a) { out.println(a); if (autoFlush) { out.flush(); } } public void println(long a) { out.println(a); if (autoFlush) { out.flush(); } } public void println(double a) { out.println(String.format("%.10f", a)); if (autoFlush) { out.flush(); } } public void println(String s) { out.println(s); if (autoFlush) { out.flush(); } } public void println(char[] s) { out.println(String.valueOf(s)); if (autoFlush) { out.flush(); } } public void println(int[] a) { StringJoiner joiner = new StringJoiner(" "); for (int i : a) { joiner.add(Integer.toString(i)); } out.println(joiner); if (autoFlush) { out.flush(); } } public void println(long[] a) { StringJoiner joiner = new StringJoiner(" "); for (long i : a) { joiner.add(Long.toString(i)); } out.println(joiner); if (autoFlush) { out.flush(); } } public void flush() { err.flush(); out.flush(); } }