結果
| 問題 | No.1244 Black Segment |
| ユーザー |
 suisen
|
| 提出日時 | 2020-10-02 22:36:06 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 34,941 bytes |
| コンパイル時間 | 4,476 ms |
| コンパイル使用メモリ | 102,552 KB |
| 実行使用メモリ | 52,132 KB |
| 最終ジャッジ日時 | 2023-09-24 21:50:26 |
| 合計ジャッジ時間 | 8,066 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | RE | - |
| testcase_01 | RE | - |
| testcase_02 | RE | - |
| testcase_03 | RE | - |
| testcase_04 | RE | - |
| testcase_05 | RE | - |
| testcase_06 | RE | - |
| testcase_07 | RE | - |
| testcase_08 | RE | - |
| testcase_09 | RE | - |
| testcase_10 | RE | - |
| testcase_11 | RE | - |
| testcase_12 | RE | - |
| testcase_13 | RE | - |
| testcase_14 | RE | - |
| testcase_15 | RE | - |
| testcase_16 | RE | - |
| testcase_17 | RE | - |
| testcase_18 | RE | - |
| testcase_19 | RE | - |
| testcase_20 | RE | - |
| testcase_21 | RE | - |
| testcase_22 | RE | - |
| testcase_23 | RE | - |
| testcase_24 | RE | - |
| testcase_25 | RE | - |
| testcase_26 | RE | - |
| testcase_27 | RE | - |
| testcase_28 | RE | - |
| testcase_29 | RE | - |
| testcase_30 | RE | - |
| testcase_31 | RE | - |
| testcase_32 | RE | - |
| testcase_33 | RE | - |
| testcase_34 | RE | - |
| testcase_35 | RE | - |
| testcase_36 | RE | - |
| testcase_37 | RE | - |
| testcase_38 | RE | - |
ソースコード
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Objects;
import java.util.TreeSet;
import java.util.function.IntPredicate;
import java.util.function.IntUnaryOperator;
import java.util.function.LongBinaryOperator;
import java.util.function.LongPredicate;
import java.util.function.LongUnaryOperator;
public class Main {
public static void main(String[] args) throws Exception {
ExtendedScanner sc = new ExtendedScanner();
FastPrintStream pw = new FastPrintStream();
solve(sc, pw);
sc.close();
pw.flush();
pw.close();
}
public static void solve(ExtendedScanner sc, FastPrintStream pw) {
int n = sc.nextInt();
int m = sc.nextInt();
int a = sc.nextInt() - 1;
int b = sc.nextInt();
TreeSet<IntPair3> set = new TreeSet<>((p1, p2) -> {
if (p1.fst == p2.fst) {
if (p1.snd == p2.snd) {
return p1.trd - p2.trd;
} else {
return p1.snd - p2.snd;
}
} else {
return p1.fst - p2.fst;
}
});
for (int i = 0; i < m; i++) {
set.add(new IntPair3(sc.nextInt() - 1, sc.nextInt(), 1));
}
ArrayList<IntPair3> lst = new ArrayList<>();
while (set.size() >= 2) {
var p1 = set.first();
var p2 = set.higher(p1);
if (p1.fst != p2.fst) {
set.remove(p1);
lst.add(p1);
} else {
if (p1.snd == p2.snd) {
set.remove(p2);
} else {
set.remove(p2);
p2.fst = p1.snd;
p2.trd += p1.trd;
set.add(p2);
}
}
}
if (set.size() == 1) {
lst.add(set.first());
}
int siz = lst.size();
IntPair3[] p = lst.toArray(IntPair3[]::new);
int[] next = new int[siz + 1];
next[siz] = siz;
Arrays.fill(next, siz);
for (int i = 0; i < siz; i++) {
int l = i, r = siz;
while (r - l > 1) {
int md = (l + r) >> 1;
if (p[md].fst == p[i].snd) {
next[i] = md;
break;
} else if (p[md].fst < p[i].snd) {
l = md;
} else {
r = md;
}
}
}
int min = Const.IINF;
Doubling d = new Doubling(next, siz);
TreeBuilder tb = new TreeBuilder(siz + 1, siz);
for (int i = 0; i < siz; i++) {
tb.addEdge(i, next[i]);
}
EulerTour et = new EulerTour(tb.build());
int[] beg = et.tourBeg;
int[] end = et.tourEnd;
int[] tour = et.tour;
int[] w = new int[2 * siz + 2];
for (int i = 0; i < 2 * siz + 2; i++) {
if (tour[i] < 0) {
if (~tour[i] == siz) {
w[i] = 0;
} else {
w[i] = -p[~tour[i]].trd;
}
} else {
if (tour[i] == siz) {
w[i] = 0;
} else {
w[i] = p[tour[i]].trd;
}
}
if (i > 0) {
w[i] += w[i - 1];
}
}
for (int i = 0; i < siz; i++) {
if (p[i].fst > a) break;
int dst = d.stepUntil(i, j -> j == siz || p[j].snd >= b);
if (dst == siz) continue;
int fr, to;
if (beg[i] >= dst) {
fr = beg[dst];
to = beg[i];
} else {
fr = beg[i];
to = beg[dst];
}
min = Math.min(min, fr > 0 ? w[to] - w[fr - 1] : w[to]);
}
if (min == Const.IINF) {
pw.println(-1);
} else {
pw.println(min);
}
}
}
/**
* @verified
* - http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_D
*/
class EulerTour {
private final int n;
public final int[] tour;
public final int[] tourBeg;
public final int[] tourEnd;
public final int[] subtBeg;
public final int[] subtEnd;
public EulerTour(Tree t) {
this.n = t.getV();
this.tour = new int[n << 1];
this.tourBeg = new int[n];
this.tourEnd = new int[n];
this.subtBeg = new int[n];
this.subtEnd = new int[n];
build(t);
}
private void build(Tree t) {
java.util.Arrays.fill(tourBeg, -1);
int[] pre = t.preOrder();
int[] pst = t.postOrder();
for (int i = 0, j = 0; j != n;) {
int u = pst[j], v;
do {
v = pre[i];
tour[i + j] = v;
tourBeg[v] = i + j;
subtBeg[v] = i;
i++;
} while (v != u);
do {
tour[i + j] = ~u;
tourEnd[u] = i + j;
subtEnd[u] = i;
j++;
} while (j < n && tourBeg[u = pst[j]] >= 0);
}
}
}
/**
* @author https://atcoder.jp/users/suisen
*/
class FastScanner implements AutoCloseable {
private final ByteBuffer tokenBuf = new ByteBuffer();
private final java.io.InputStream in;
private final byte[] rawBuf = new byte[1 << 14];
private int ptr = 0;
private int buflen = 0;
public FastScanner(java.io.InputStream in) {
this.in = in;
}
public FastScanner() {
this(new java.io.FileInputStream(java.io.FileDescriptor.in));
}
private final int readByte() {
if (ptr < buflen) return rawBuf[ptr++];
ptr = 0;
try {
buflen = in.read(rawBuf);
if (buflen > 0) {
return rawBuf[ptr++];
} else {
throw new java.io.EOFException();
}
} catch (java.io.IOException e) {
throw new java.io.UncheckedIOException(e);
}
}
private final int readByteUnsafe() {
if (ptr < buflen) return rawBuf[ptr++];
ptr = 0;
try {
buflen = in.read(rawBuf);
if (buflen > 0) {
return rawBuf[ptr++];
} else {
return -1;
}
} catch (java.io.IOException e) {
throw new java.io.UncheckedIOException(e);
}
}
private final int skipUnprintableChars() {
int b = readByte();
while (b <= 32 || b >= 127) b = readByte();
return b;
}
private final void loadToken() {
tokenBuf.clear();
for (int b = skipUnprintableChars(); 32 < b && b < 127; b = readByteUnsafe()) {
tokenBuf.append(b);
}
}
public final boolean hasNext() {
for (int b = readByteUnsafe(); b <= 32 || b >= 127; b = readByteUnsafe()) {
if (b == -1) return false;
}
--ptr;
return true;
}
public final String next() {
loadToken();
return new String(tokenBuf.getRawBuf(), 0, tokenBuf.size());
}
public final String nextLine() {
tokenBuf.clear();
for (int b = readByte(); b != '\n'; b = readByteUnsafe()) {
if (b == -1) break;
tokenBuf.append(b);
}
return new String(tokenBuf.getRawBuf(), 0, tokenBuf.size());
}
public final char nextChar() {
return (char) skipUnprintableChars();
}
public final char[] nextChars() {
loadToken();
return tokenBuf.toCharArray();
}
public final long nextLong() {
long n = 0;
boolean isNegative = false;
int b = skipUnprintableChars();
if (b == '-') {
isNegative = true;
b = readByteUnsafe();
}
if (b < '0' || '9' < b) throw new NumberFormatException();
while ('0' <= b && b <= '9') {
// -9223372036854775808 - 9223372036854775807
if (n >= 922337203685477580l) {
if (n > 922337203685477580l) {
throw new ArithmeticException("long overflow");
}
if (isNegative) {
if (b >= '9') {
throw new ArithmeticException("long overflow");
}
n = -n - (b + '0');
b = readByteUnsafe();
if ('0' <= b && b <= '9') {
throw new ArithmeticException("long overflow");
} else if (b <= 32 || b >= 127) {
return n;
} else {
throw new NumberFormatException();
}
} else {
if (b >= '8') {
throw new ArithmeticException("long overflow");
}
n = n * 10 + b - '0';
b = readByteUnsafe();
if ('0' <= b && b <= '9') {
throw new ArithmeticException("long overflow");
} else if (b <= 32 || b >= 127) {
return n;
} else {
throw new NumberFormatException();
}
}
}
n = n * 10 + b - '0';
b = readByteUnsafe();
}
if (b <= 32 || b >= 127) return isNegative ? -n : n;
throw new NumberFormatException();
}
public final int nextInt() {
long value = nextLong();
if ((int) value != value) {
throw new ArithmeticException("int overflow");
}
return (int) value;
}
public final double nextDouble() {
return Double.parseDouble(next());
}
public final void close() {
try {
in.close();
} catch (java.io.IOException e) {
throw new java.io.UncheckedIOException(e);
}
}
private static final class ByteBuffer {
private static final int DEFAULT_BUF_SIZE = 1 << 12;
private byte[] buf;
private int ptr = 0;
private ByteBuffer(int capacity) {
this.buf = new byte[capacity];
}
private ByteBuffer() {
this(DEFAULT_BUF_SIZE);
}
private ByteBuffer append(int b) {
if (ptr == buf.length) {
int newLength = buf.length << 1;
byte[] newBuf = new byte[newLength];
System.arraycopy(buf, 0, newBuf, 0, buf.length);
buf = newBuf;
}
buf[ptr++] = (byte) b;
return this;
}
private char[] toCharArray() {
char[] chs = new char[ptr];
for (int i = 0; i < ptr; i++) {
chs[i] = (char) buf[i];
}
return chs;
}
private byte[] getRawBuf() {
return buf;
}
private int size() {
return ptr;
}
private void clear() {
ptr = 0;
}
}
}
class TreeBuilder {
private static final class TreeEdge {
final int from, to;
final long cost;
TreeEdge(int from, int to, long cost) {
this.from = from;
this.to = to;
this.cost = cost;
}
}
private final int n;
private int ptr = 0;
private final int root;
private final TreeEdge[] edges;
private final int[] count;
private final int[][] adj;
public TreeBuilder(int n, int root) {
this.n = n;
this.root = root;
this.edges = new TreeEdge[n - 1];
this.count = new int[n];
this.adj = new int[n][];
}
public TreeBuilder(int n) {
this(n, 0);
}
public void addEdge(int u, int v, long cost) {
edges[ptr++] = new TreeEdge(u, v, cost);
count[u]++;
count[v]++;
}
public void addEdge(int u, int v) {
addEdge(u, v, 1);
}
public Tree build() {
for (int i = 0; i < n; i++) {
adj[i] = new int[count[i]];
}
for (TreeEdge e : edges) {
int u = e.from;
int v = e.to;
adj[u][--count[u]] = v;
adj[v][--count[v]] = u;
}
return new Tree(n, root, adj);
}
public WeightedTree buildWeightedTree() {
long[][] cst = new long[n][];
for (int i = 0; i < n; i++) {
adj[i] = new int[count[i]];
cst[i] = new long[count[i]];
}
for (TreeEdge e : edges) {
int u = e.from;
int v = e.to;
adj[u][--count[u]] = v;
adj[v][--count[v]] = u;
cst[u][count[u]] = e.cost;
cst[v][count[v]] = e.cost;
}
return new WeightedTree(n, root, adj, cst);
}
}
/**
* @author https://atcoder.jp/users/suisen
*/
final class ExtendedScanner extends FastScanner {
public ExtendedScanner() {super();}
public ExtendedScanner(InputStream in) {super(in);}
public int[] ints(final int n) {
final int[] a = new int[n];
Arrays.setAll(a, $ -> nextInt());
return a;
}
public int[] ints(final int n, final IntUnaryOperator f) {
final int[] a = new int[n];
Arrays.setAll(a, $ -> f.applyAsInt(nextInt()));
return a;
}
public int[][] ints(final int n, final int m) {
final int[][] a = new int[n][];
Arrays.setAll(a, $ -> ints(m));
return a;
}
public int[][] ints(final int n, final int m, final IntUnaryOperator f) {
final int[][] a = new int[n][];
Arrays.setAll(a, $ -> ints(m, f));
return a;
}
public long[] longs(final int n) {
final long[] a = new long[n];
Arrays.setAll(a, $ -> nextLong());
return a;
}
public long[] longs(final int n, final LongUnaryOperator f) {
final long[] a = new long[n];
Arrays.setAll(a, $ -> f.applyAsLong(nextLong()));
return a;
}
public long[][] longs(final int n, final int m) {
final long[][] a = new long[n][];
Arrays.setAll(a, $ -> longs(m));
return a;
}
public long[][] longs(final int n, final int m, final LongUnaryOperator f) {
final long[][] a = new long[n][];
Arrays.setAll(a, $ -> longs(m, f));
return a;
}
public char[][] charArrays(final int n) {
final char[][] c = new char[n][];
Arrays.setAll(c, $ -> nextChars());
return c;
}
public double[] doubles(final int n) {
final double[] a = new double[n];
Arrays.setAll(a, $ -> nextDouble());
return a;
}
public double[][] doubles(final int n, final int m) {
final double[][] a = new double[n][];
Arrays.setAll(a, $ -> doubles(m));
return a;
}
public String[] strings(final int n) {
final String[] s = new String[n];
Arrays.setAll(s, $ -> next());
return s;
}
}
/**
* @author https://atcoder.jp/users/suisen
*/
class FastPrintStream implements AutoCloseable {
private static final int INT_MAX_LEN = 11;
private static final int LONG_MAX_LEN = 20;
private int precision = 9;
private static final int BUF_SIZE = 1 << 14;
private static final int BUF_SIZE_MINUS_INT_MAX_LEN = BUF_SIZE - INT_MAX_LEN;
private static final int BUF_SIZE_MINUS_LONG_MAX_LEN = BUF_SIZE - LONG_MAX_LEN;
private final byte[] buf = new byte[BUF_SIZE];
private int ptr = 0;
private final java.lang.reflect.Field strField;
private final java.nio.charset.CharsetEncoder encoder;
private final java.io.OutputStream out;
public FastPrintStream(java.io.OutputStream out) {
this.out = out;
java.lang.reflect.Field f;
try {
f = java.lang.String.class.getDeclaredField("value");
f.setAccessible(true);
} catch (NoSuchFieldException | SecurityException e) {
f = null;
}
this.strField = f;
this.encoder = java.nio.charset.StandardCharsets.US_ASCII.newEncoder();
}
public FastPrintStream(java.io.File file) throws java.io.IOException {
this(new java.io.FileOutputStream(file));
}
public FastPrintStream(java.lang.String filename) throws java.io.IOException {
this(new java.io.File(filename));
}
public FastPrintStream() {
this(new java.io.FileOutputStream(java.io.FileDescriptor.out));
}
public FastPrintStream println() {
if (ptr == BUF_SIZE) internalFlush();
buf[ptr++] = (byte) '\n';
return this;
}
public FastPrintStream println(java.lang.Object o) {
return print(o).println();
}
public FastPrintStream println(java.lang.String s) {
return print(s).println();
}
public FastPrintStream println(char[] s) {
return print(s).println();
}
public FastPrintStream println(char c) {
return print(c).println();
}
public FastPrintStream println(int x) {
return print(x).println();
}
public FastPrintStream println(long x) {
return print(x).println();
}
public FastPrintStream println(double d, int precision) {
return print(d, precision).println();
}
public FastPrintStream println(double d) {
return print(d).println();
}
private FastPrintStream print(byte[] bytes) {
int n = bytes.length;
if (ptr + n > BUF_SIZE) {
internalFlush();
try {
out.write(bytes);
} catch (java.io.IOException e) {
throw new java.io.UncheckedIOException(e);
}
} else {
System.arraycopy(bytes, 0, buf, ptr, n);
ptr += n;
}
return this;
}
public FastPrintStream print(java.lang.Object o) {
return print(o.toString());
}
public FastPrintStream print(java.lang.String s) {
if (strField == null) {
return print(s.getBytes());
} else {
try {
Object value = strField.get(s);
if (value instanceof byte[]) {
return print((byte[]) value);
} else {
return print((char[]) value);
}
} catch (IllegalAccessException e) {
return print(s.getBytes());
}
}
}
public FastPrintStream print(char[] s) {
try {
return print(encoder.encode(java.nio.CharBuffer.wrap(s)).array());
} catch (java.nio.charset.CharacterCodingException e) {
byte[] bytes = new byte[s.length];
for (int i = 0; i < s.length; i++) {
bytes[i] = (byte) s[i];
}
return print(bytes);
}
}
public FastPrintStream print(char c) {
if (ptr == BUF_SIZE) internalFlush();
buf[ptr++] = (byte) c;
return this;
}
public FastPrintStream print(int x) {
if (ptr > BUF_SIZE_MINUS_INT_MAX_LEN) internalFlush();
if (-10 < x && x < 10) {
if (x < 0) {
buf[ptr++] = '-';
x = -x;
}
buf[ptr++] = (byte) ('0' + x);
return this;
}
int d;
if (x < 0) {
if (x == Integer.MIN_VALUE) {
buf[ptr++] = '-'; buf[ptr++] = '2'; buf[ptr++] = '1'; buf[ptr++] = '4';
buf[ptr++] = '7'; buf[ptr++] = '4'; buf[ptr++] = '8'; buf[ptr++] = '3';
buf[ptr++] = '6'; buf[ptr++] = '4'; buf[ptr++] = '8';
return this;
}
d = len(x = -x);
buf[ptr++] = '-';
} else {
d = len(x);
}
int j = ptr += d;
while (x > 0) {
buf[--j] = (byte) ('0' + (x % 10));
x /= 10;
}
return this;
}
public FastPrintStream print(long x) {
if ((int) x == x) return print((int) x);
if (ptr > BUF_SIZE_MINUS_LONG_MAX_LEN) internalFlush();
int d;
if (x < 0) {
if (x == Long.MIN_VALUE) {
buf[ptr++] = '-'; buf[ptr++] = '9'; buf[ptr++] = '2'; buf[ptr++] = '2';
buf[ptr++] = '3'; buf[ptr++] = '3'; buf[ptr++] = '7'; buf[ptr++] = '2';
buf[ptr++] = '0'; buf[ptr++] = '3'; buf[ptr++] = '6'; buf[ptr++] = '8';
buf[ptr++] = '5'; buf[ptr++] = '4'; buf[ptr++] = '7'; buf[ptr++] = '7';
buf[ptr++] = '5'; buf[ptr++] = '8'; buf[ptr++] = '0'; buf[ptr++] = '8';
return this;
}
d = len(x = -x);
buf[ptr++] = '-';
} else {
d = len(x);
}
int j = ptr += d;
while (x > 0) {
buf[--j] = (byte) ('0' + (x % 10));
x /= 10;
}
return this;
}
public FastPrintStream print(double d, int precision) {
if (d < 0) {
print('-');
d = -d;
}
d += Math.pow(10, -precision) / 2;
print((long) d).print('.');
d -= (long) d;
for(int i = 0; i < precision; i++){
d *= 10;
print((int) d);
d -= (int) d;
}
return this;
}
public FastPrintStream print(double d) {
return print(d, precision);
}
public void setPrecision(int precision) {
this.precision = precision;
}
private void internalFlush() {
try {
out.write(buf, 0, ptr);
ptr = 0;
} catch (java.io.IOException e) {
throw new java.io.UncheckedIOException(e);
}
}
public void flush() {
try {
out.write(buf, 0, ptr);
out.flush();
ptr = 0;
} catch (java.io.IOException e) {
throw new java.io.UncheckedIOException(e);
}
}
public void close() {
try {
out.close();
} catch (java.io.IOException e) {
throw new java.io.UncheckedIOException(e);
}
}
private static int len(int x) {
return
x >= 1000000000 ? 10 :
x >= 100000000 ? 9 :
x >= 10000000 ? 8 :
x >= 1000000 ? 7 :
x >= 100000 ? 6 :
x >= 10000 ? 5 :
x >= 1000 ? 4 :
x >= 100 ? 3 :
x >= 10 ? 2 : 1;
}
private static int len(long x) {
return
x >= 1000000000000000000l ? 19 :
x >= 100000000000000000l ? 18 :
x >= 10000000000000000l ? 17 :
x >= 1000000000000000l ? 16 :
x >= 100000000000000l ? 15 :
x >= 10000000000000l ? 14 :
x >= 1000000000000l ? 13 :
x >= 100000000000l ? 12 :
x >= 10000000000l ? 11 : 10;
}
}
/**
* @author https://atcoder.jp/users/suisen
*/
@FunctionalInterface
interface IntBiPredicate {
static final int INT_BIT = 32;
static final long MASK = 0xffff_ffffl;
public boolean test(int x, int y);
default public IntPredicate curry(final int x) {return y -> test(x, y);}
default public LongPredicate toLongPredicate() {return l -> test((int) (l >>> INT_BIT), (int) (l & MASK));}
default public IntBiPredicate negate() {return (x, y) -> !test(x, y);}
default public IntBiPredicate and(final IntBiPredicate other) {return (x, y) -> test(x, y) && other.test(x, y);}
default public IntBiPredicate or(final IntBiPredicate other) {return (x, y) -> test(x, y) || other.test(x, y);}
default public IntBiPredicate xor(final IntBiPredicate other) {return (x, y) -> test(x, y) ^ other.test(x, y);}
}
class Const {
public static final long LINF = 1l << 59;
public static final int IINF = (1 << 30) - 1;
public static final double DINF = 1e150;
public static final double SMALL = 1e-12;
public static final double MEDIUM = 1e-9;
public static final double LARGE = 1e-6;
public static final long MOD1000000007 = 1000000007;
public static final long MOD998244353 = 998244353 ;
public static final long MOD754974721 = 754974721 ;
public static final long MOD167772161 = 167772161 ;
public static final long MOD469762049 = 469762049 ;
public static final int[] dx8 = {1, 0, -1, 0, 1, -1, -1, 1};
public static final int[] dy8 = {0, 1, 0, -1, 1, 1, -1, -1};
public static final int[] dx4 = {1, 0, -1, 0};
public static final int[] dy4 = {0, 1, 0, -1};
}
/**
* @author https://atcoder.jp/users/suisen
*/
class Tree {
final int n;
final int root;
final int[][] adj;
final int[] par;
final int[] pre;
final int[] pst;
Tree(int n, int root, int[][] adj) {
this.n = n;
this.adj = adj;
this.root = root;
this.par = new int[n];
this.pre = new int[n];
this.pst = new int[n];
build();
}
private void build() {
int preOrd = 0, pstOrd = 0;
java.util.Arrays.fill(par, -1);
int[] stack = new int[n << 1];
int ptr = 0;
stack[ptr++] = ~root;
stack[ptr++] = root;
while (ptr > 0) {
int u = stack[--ptr];
if (u >= 0) {
pre[preOrd++] = u;
for (int v : adj[u]) {
if (v == par[u]) continue;
par[v] = u;
stack[ptr++] = ~v;
stack[ptr++] = v;
}
} else {
pst[pstOrd++] = ~u;
}
}
}
public int getV() {
return n;
}
public int getRoot() {
return root;
}
public int[] getEdges(int u) {
return adj[u];
}
public int[] parent() {
return par;
}
public int[] preOrder() {
return pre;
}
public int[] postOrder() {
return pst;
}
}
/**
* @author https://atcoder.jp/users/suisen
*/
final class IntPair3 {
public int fst, snd, trd;
public IntPair3(final int fst, final int snd, final int trd) {this.fst = fst; this.snd = snd; this.trd = trd;}
@Override @SuppressWarnings("all")
public boolean equals(final Object o) {
if (this == o) return true;
if (!(o instanceof IntPair3)) return false;
final IntPair3 p = (IntPair3) o;
return this.fst == p.fst && this.snd == p.snd && this.trd == p.trd;
}
@Override
public int hashCode() {return Objects.hash(this.fst, this.snd, this.trd);}
@Override
public String toString() {return "(" + this.fst + ", " + this.snd + ", " + this.trd + ")";}
}
/**
* @author https://atcoder.jp/users/suisen
*/
final class Longs {
private Longs(){}
public static long max(long a, long b) {
return Math.max(a, b);
}
public static long max(long a, long b, long c) {
return Math.max(Math.max(a, b), c);
}
public static long max(long a, long b, long c, long d) {
return Math.max(Math.max(Math.max(a, b), c), d);
}
public static long max(long a, long b, long c, long d, long e) {
return Math.max(Math.max(Math.max(Math.max(a, b), c), d), e);
}
public static long max(long a, long b, long c, long d, long e, long f) {
return Math.max(Math.max(Math.max(Math.max(Math.max(a, b), c), d), e), f);
}
public static long max(long a, long b, long c, long d, long e, long f, long g) {
return Math.max(Math.max(Math.max(Math.max(Math.max(Math.max(a, b), c), d), e), f), g);
}
public static long max(long a, long b, long c, long d, long e, long f, long g, long h) {
return Math.max(Math.max(Math.max(Math.max(Math.max(Math.max(Math.max(a, b), c), d), e), f), g), h);
}
public static long max(long a, long... vals) {
long ret = a; for (long e : vals) ret = Math.max(ret, e);
return ret;
}
public static long min(long a, long b) {
return Math.min(a, b);
}
public static long min(long a, long b, long c) {
return Math.min(Math.min(a, b), c);
}
public static long min(long a, long b, long c, long d) {
return Math.min(Math.min(Math.min(a, b), c), d);
}
public static long min(long a, long b, long c, long d, long e) {
return Math.min(Math.min(Math.min(Math.min(a, b), c), d), e);
}
public static long min(long a, long b, long c, long d, long e, long f) {
return Math.min(Math.min(Math.min(Math.min(Math.min(a, b), c), d), e), f);
}
public static long min(long a, long b, long c, long d, long e, long f, long g) {
return Math.min(Math.min(Math.min(Math.min(Math.min(Math.min(a, b), c), d), e), f), g);
}
public static long min(long a, long b, long c, long d, long e, long f, long g, long h) {
return Math.min(Math.min(Math.min(Math.min(Math.min(Math.min(Math.min(a, b), c), d), e), f), g), h);
}
public static long min(long a, long... vals) {
long ret = a; for (long e : vals) ret = Math.min(ret, e);
return ret;
}
public static long fold(final LongBinaryOperator func, final long... a) {
long ret = a[0]; for (int i = 1; i < a.length; i++) ret = func.applyAsLong(ret, a[i]);
return ret;
}
public static boolean isPowerOfTwo(final long n) {return n != 0 && (-n & n) == n;}
public static int ceilExponent(final long n) {return 63 - Long.numberOfLeadingZeros(n) + (isPowerOfTwo(n) ? 0 : 1);}
public static int floorExponent(final long n) {return 63 - Long.numberOfLeadingZeros(n) + (n == 0 ? 1 : 0);}
public static int ceilExponent(final long n, final int base) {
if (base == 2) return ceilExponent(n);
int i = 0;
long m = 1;
while (m < n) {
i++;
final long r = m * base;
if ((m | base) >> 31 != 0 && r / base != m) break;
m = r;
}
return i;
}
/**
* Caluculate the ceil of a/b. Returns the smallest integer greater than or
* equal to a/b while 'a/b' rounds fractional parts to ZERO.
* @param a
* @param b
* @return the smallest integer greater than or equal to a/b
*/
public static long cld(final long a, final long b) {
if (a > 0 && b > 0) return (a + b - 1) / b;
if (a < 0 && b < 0) return (a + b + 1) / b;
return a / b;
}
/**
* Caluculate the floor of a/b. Returns the largest integer less than or equal
* to a/b while 'a/b' rounds fractional parts to ZERO.
* @param a
* @param b
* @return the largest integer less than or equal to a/b
*/
public static long fld(final long a, final long b) {
if (a <= 0 && b > 0) return (a - b + 1) / b;
if (a > 0 && b <= 0) return (a - b - 1) / b;
return a / b;
}
public static String join(final String sep, final long... a) {
final StringBuilder sb = new StringBuilder();
for (int i = 0; i < a.length; i++) {
sb.append(a[i]);
if (i < a.length - 1) sb.append(sep);
}
return sb.toString();
}
}
/**
* @author https://atcoder.jp/users/suisen
*/
final class Doubling {
public final int[][] doubling;
private final int height;
private final int n;
public Doubling(final int[] a, final long maxStep) {
this.n = a.length;
this.height = Longs.ceilExponent(maxStep) + 2;
this.doubling = new int[height][n];
build(a);
}
public int getHeight() {return height;}
public int query(int i, long step) {
int h = height - 1;
while (step > 0) {
if ((step & (1l << h)) != 0) {
i = doubling[h][i];
step ^= 1l << h;
}
h--;
}
return i;
}
public int stepWhile(int i, final IntPredicate p) {
int h = height - 1;
while (h >= 0) {
if (p.test(doubling[h][i])) i = doubling[h][i];
h--;
}
return i;
}
public int stepUntil(final int i, final IntPredicate p) {return p.test(i) ? i : doubling[0][stepWhile(i, p.negate())];}
public int[] biStep(final int u, final int v, final int exponent) {
final int us = doubling[exponent][u];
final int vs = doubling[exponent][v];
return new int[]{us, vs};
}
private long biStep(final long uv, final int exponent) {
final int u = (int) (uv >>> 32);
final int v = (int) (uv & 0xffff_ffffl);
return (long) doubling[exponent][u] << 32 | doubling[exponent][v];
}
public int[] biStepWhile(final int u, final int v, final IntBiPredicate p) {
final long ret = biStepWhile((long) u << 32 | v, p.toLongPredicate());
return new int[]{(int) (ret >> 32), (int) (ret & 0xffff_ffffl)};
}
private long biStepWhile(long uv, final LongPredicate p) {
int h = height - 1;
while (h >= 0) {
final long step = biStep(uv, h);
if (p.test(step)) {
uv = step;
}
h--;
}
return uv;
}
public int[] biStepUntil(final int u, final int v, final IntBiPredicate p) {
final long ret = biStepUntil((long) u << 32 | v, p.toLongPredicate());
return new int[]{(int) (ret >> 32), (int) (ret & 0xffff_ffffl)};
}
private long biStepUntil(final long uv, final LongPredicate p) {return p.test(uv) ? uv : biStep(biStepWhile(uv, p.negate()), 0);}
public int[] parallelStep(final int[] a, final int exponent) {
final int[] ret = a.clone();
for (int i = 0; i < a.length; i++) ret[i] = doubling[exponent][a[i]];
return ret;
}
private void build(final int[] a) {
doubling[0] = a;
for (int h = 1; h < height; h++) for (int i = 0; i < n; i++) doubling[h][i] = doubling[h - 1][doubling[h - 1][i]];
}
}
/**
* @author https://atcoder.jp/users/suisen
*/
class WeightedTree extends Tree {
final long[] cst;
final long[][] adjCost;
WeightedTree(int n, int root, int[][] adj, long[][] adjCost) {
super(n, root, adj);
this.cst = new long[n];
this.adjCost = adjCost;
for (int u = 0; u < n; u++) {
int k = adj[u].length;
for (int i = 0; i < k; i++) {
int v = adj[u][i];
long c = adjCost[u][i];
if (v == par[u]) {
cst[u] = c;
} else {
cst[v] = c;
}
}
}
}
public long[] getWeights() {
return cst;
}
public long getWeight(int u, int i) {
return adjCost[u][i];
}
}