結果
| 問題 |
No.2634 Tree Distance 3
|
| コンテスト | |
| ユーザー |
 Yu_212
|
| 提出日時 | 2024-02-19 01:16:04 |
| 言語 | Java (openjdk 23) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 18,013 bytes |
| コンパイル時間 | 3,254 ms |
| コンパイル使用メモリ | 100,376 KB |
| 実行使用メモリ | 563,292 KB |
| 最終ジャッジ日時 | 2024-09-29 01:04:51 |
| 合計ジャッジ時間 | 13,873 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 2 |
| other | MLE * 1 -- * 68 |
ソースコード
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<List<Integer>> edges = in.nextGraph(n, n - 1, false);
new CentroidDecomposition(edges) {
void query(int center, List<List<Integer>> left, List<List<Integer>> right) {
f(center, left, right);
f(center, right, left);
}
};
out.println(ans);
}
List<Integer> table;
void f(int s, List<List<Integer>> x, List<List<Integer>> 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<List<Integer>> 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<List<Integer>> 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<List<List<Integer>>> bufLeft = new ArrayList<>();
List<List<List<Integer>>> bufRight = new ArrayList<>();
abstract void query(int center, List<List<Integer>> left, List<List<Integer>> right);
public CentroidDecomposition(List<List<Integer>> 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<List<Integer>> 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<List<Integer>> edgesLeft = new ArrayList<>();
List<List<Integer>> 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<List<Integer>> left = bufLeft.get(depth);
List<List<Integer>> right = bufRight.get(depth);
left.get(s).clear();
right.get(s).clear();
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<List<Integer>> edges, List<List<Integer>> sub) {
sub.set(node, new ArrayList<>(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<List<Integer>> 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 center;
int n;
List<List<List<Integer>>> bufLeft = new ArrayList<>();
List<List<List<Integer>>> bufRight = new ArrayList<>();
abstract void query(int center, List<List<Integer>> left, List<List<Integer>> right);
public CentroidDecomposition2(List<List<Integer>> 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<List<Integer>> edges, int depth) {
if (m <= 2) {
return;
}
center = -1;
size(root, -1, m, edges);
int max = 0;
for (int nei : edges.get(center)) {
if (size[nei] > size[center]) {
size[nei] = m - size[center];
}
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(center)) {
sort[--count[size[nei]]] = nei;
}
Arrays.fill(count, 0, max, 0);
int xs = 0;
int ys = 0;
int g = edges.get(center).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<List<Integer>> edgesLeft = new ArrayList<>();
List<List<Integer>> 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<List<Integer>> left = bufLeft.get(depth);
List<List<Integer>> right = bufRight.get(depth);
left.get(center).clear();
right.get(center).clear();
for (int nei : edges.get(center)) {
if (xy[nei]) {
right.get(center).add(nei);
build(nei, center, edges, right);
} else {
left.get(center).add(nei);
build(nei, center, edges, left);
}
}
query(center, left, right);
rec(xs + 1, center, left, depth + 1);
rec(ys + 1, center, right, depth + 1);
}
private void build(int root, int par, List<List<Integer>> edges, List<List<Integer>> 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<Integer> deque = new ArrayDeque<>();
private void size(int root, int par, int m, List<List<Integer>> edges) {
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) {
center = u;
}
} else {
for (int child : edges.get(u)) {
if (child != parent[u]) {
parent[child] = u;
size[child] = 1;
deque.addLast(~child);
deque.addLast(child);
}
}
}
}
}
}
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<List<Integer>> nextGraph(int n, int m, boolean directed) {
List<List<Integer>> 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();
}
}