結果
| 問題 |
No.1344 Typical Shortest Path Sum
|
| コンテスト | |
| ユーザー |
 ks2m
|
| 提出日時 | 2021-01-16 15:46:19 |
| 言語 | Java (openjdk 23) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 54,223 bytes |
| コンパイル時間 | 7,364 ms |
| コンパイル使用メモリ | 110,808 KB |
| 実行使用メモリ | 56,564 KB |
| 最終ジャッジ日時 | 2024-11-27 18:41:03 |
| 合計ジャッジ時間 | 19,868 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | RE * 3 |
| other | RE * 77 |
ソースコード
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.function.BiFunction;
public class Sample {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.close();
for (int i = 0; i < n; i++) {
}
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int c = Integer.parseInt(br.readLine());
String[] sa = br.readLine().split(" ");
int a = Integer.parseInt(sa[0]);
int b = Integer.parseInt(sa[1]);
String s = br.readLine();
br.close();
System.out.println(a + b + c + s);
PrintWriter pw = new PrintWriter(System.out);
pw.println(123);
pw.flush();
pw.close();
// 2^nの全探索
int end = 1 << n;
for (int i = 0; i < end; i++) {
for (int j = 0; j < n; j++) {
if ((i >> j & 1) == 1) {
}
}
}
// 二分探索（探索値以上の最小のインデックス）
int[] array = new int[5];
int idx = Arrays.binarySearch(array, 5);
if (idx < 0) idx = ~idx;
// grundy数
// 遷移先のgrundy数の集合に含まれない最小の0以上の整数
}
/**
* 木の入力を受け取る
* N
* A1 B1
* ・
* ・
* An-1 Bn-1
* 頂点の番号(0-indexed)＜連結頂点リスト＞
*/
static List<List<Integer>> inputTree() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] sa = br.readLine().split(" ");
int n = Integer.parseInt(sa[0]);
List<List<Integer>> list = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
list.add(new ArrayList<>());
}
for (int i = 0; i < n - 1; i++) {
sa = br.readLine().split(" ");
int a = Integer.parseInt(sa[0]) - 1;
int b = Integer.parseInt(sa[1]) - 1;
list.get(a).add(b);
list.get(b).add(a);
}
br.close();
return list;
}
/**
* 木において、根から近い順の頂点番号のリストを取得する
* ※BFSで訪れた頂点の順に追加したリストを作成
* 逆順に参照すれば、根から遠い順に処理を行うことができる
*/
static List<Integer> nearRootList() throws Exception {
int n = 5;
List<List<Integer>> list = inputTree();
List<Integer> near = new ArrayList<Integer>(n);
boolean[] visit = new boolean[n];
Queue<Integer> que = new ArrayDeque<Integer>();
near.add(0);
que.add(0);
visit[0] = true;
while (!que.isEmpty()) {
Integer cur = que.poll();
for (Integer next : list.get(cur)) {
if (!visit[next]) {
near.add(next);
que.add(next);
visit[next] = true;
}
}
}
return near;
}
/**
* 二分探索
*
* @param array 配列
* @param val 探索値
* @return 探索値以上の最小のインデックス（探索値と同値が複数ある場合は保証なし）
*/
static int binarySearch(long[] array, long val) {
int ok = array.length;
int ng = -1;
while (Math.abs(ok - ng) > 1) {
int mid = (ok + ng) / 2;
if (array[mid] >= val) {
ok = mid;
} else {
ng = mid;
}
}
return ok;
}
/**
* 三分探索
* @return
*/
static double ternarySearch() {
double gosa = 1e-8;
double l = 0;
double r = 1e9;
// 計算結果の差にしないと駄目かも
while (r - l > gosa) {
double m1 = (l * 2 + r) / 3;
double m2 = (l + r * 2) / 3;
double v1 = m1; // calc(m1)
double v2 = m2;
if (v1 <= v2) {
r = m2;
} else {
l = m1;
}
}
return r; // calc(r)
}
/**
* 配列を逆順にする
*/
static void reverse(int[] a) {
for (int i = 0; i < a.length / 2; i++) {
int tmp = a[i];
a[i] = a[a.length - 1 - i];
a[a.length - 1 - i] = tmp;
}
}
/**
* Beanのソート
*/
static void beanSort() {
// vの降順
Hoge[] array = new Hoge[5];
Arrays.sort(array, new Comparator<Hoge>() {
public int compare(Hoge o1, Hoge o2) {
return o2.v - o1.v;
}
});
// プライオリティキュー
PriorityQueue<Hoge> pq = new PriorityQueue<Hoge>();
pq.add(new Hoge(1, 2));
pq.poll();
// Integer降順
PriorityQueue<Integer> que2 = new PriorityQueue<>((o1, o2) -> o2 - o1);
que2.poll();
}
static class Hoge implements Comparable<Hoge>{
int a;
int b;
int v;
public Hoge(int a, int b) {
this.a = a;
this.b = b;
this.v = a + b;
}
public int compareTo(Hoge o) {
return v - o.v;
}
}
/**
* 配列をセットやマップのキーにしたい場合
* （カンマ区切りで文字列化とかした場合とどっちが速いかは不明）
*/
static class ArrayObj {
int[] arr;
int code = 0;
public ArrayObj(int[] a) {
arr = new int[a.length];
System.arraycopy(a, 0, arr, 0, a.length);
code = Arrays.hashCode(arr);
}
@Override
public boolean equals(Object o) {
ArrayObj ao = (ArrayObj) o;
for (int i = 0; i < arr.length; i++) {
if (arr[i] != ao.arr[i]) {
return false;
}
}
return true;
}
@Override
public int hashCode() {
return code;
}
}
/**
* 階乗とその逆元の事前計算（実行時間約200ms）
*/
static void kaijou() {
int n = 1000001;
int mod = 1000000007;
long[] p = new long[n];
long[] pi = new long[n];
p[0] = 1;
pi[0] = 1;
for (int i = 1; i < n; i++) {
p[i] = p[i - 1] * i % mod;
}
pi[n - 1] = BigInteger.valueOf(p[n - 1])
.modInverse(BigInteger.valueOf(mod)).longValue();
for (int i = n - 1; i > 1; i--) {
pi[i - 1] = pi[i] * i % mod;
}
}
/**
* 二項係数
* 組み合わせの数nCrをmodで割った余りを求められるように階乗を前計算 O(n)
* ↓modを取らないもの
* https://atcoder.jp/contests/abc011/submissions/11238811
*/
static class Kaijou {
long[] p, pi;
int m;
public Kaijou(int n, int mod) {
n++;
m = mod;
p = new long[n];
pi = new long[n];
p[0] = 1;
pi[0] = 1;
for (int i = 1; i < n; i++) {
p[i] = p[i - 1] * i % m;
}
pi[n - 1] = BigInteger.valueOf(p[n - 1])
.modInverse(BigInteger.valueOf(m)).longValue();
for (int i = n - 1; i > 1; i--) {
pi[i - 1] = pi[i] * i % m;
}
}
public long comb(int n, int r) {
if (n < r) return 0;
return p[n] * pi[r] % m * pi[n - r] % m;
}
public long perm(int n, int r) {
if (n < r) return 0;
return p[n] * pi[n - r] % m;
}
}
/**
* 組み合わせの数nCr O(r)
*/
static long nCr(int n, int r) {
long val = 1;
for (int i = 1; i <= r; i++) {
val = val * (n - i + 1) / i;
}
return val;
}
/**
* 組み合わせの数nCrをmで割った余り O(r)
*/
static long nCr(int n, int r, int m) {
long val = 1;
for (int i = 1; i <= r; i++) {
val = val * (n - i + 1) % m;
val = val * modinv(i, m) % m;
}
return val;
}
static long nCr(long n, int r, int m) {
long val = 1;
for (int i = 1; i <= r; i++) {
val = val * ((n - i + 1) % m) % m;
val = val * modinv(i, m) % m;
}
return val;
}
/**
* aのmod mでの逆元
*/
static long modinv(long a, int m) {
long b = m;
long u = 1;
long v = 0;
long tmp = 0;
while (b > 0) {
long t = a / b;
a -= t * b;
tmp = a;
a = b;
b = tmp;
u -= t * v;
tmp = u;
u = v;
v = tmp;
}
u %= m;
if (u < 0) u += m;
return u;
}
/**
* パスカルの三角形（実行時間約130ms）
*/
static int[][] pascal() {
int n = 5000;
int m = 1000000007;
int[][] pas = new int[n + 1][n + 1];
pas[0][0] = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
pas[i + 1][j] += pas[i][j];
pas[i + 1][j + 1] += pas[i][j];
pas[i + 1][j] %= m;
pas[i + 1][j + 1] %= m;
}
}
return pas;
}
/**
* エラトステネスの篩
* 2～nの素因数分解ができるように前計算
*/
static class Eratosthenes {
int[] div;
public Eratosthenes(int n) {
if (n < 2) return;
div = new int[n + 1];
div[0] = -1;
div[1] = -1;
int end = (int) Math.sqrt(n) + 1;
for (int i = 2; i <= end; i++) {
if (div[i] == 0) {
div[i] = i;
for (int j = i * i; j <= n; j+=i) {
if (div[j] == 0) div[j] = i;
}
}
}
for (int i = end + 1; i <= n; i++) {
if (div[i] == 0) div[i] = i;
}
}
public Map<Integer, Integer> bunkai(int x) {
Map<Integer, Integer> soinsu = new HashMap<>();
while (x > 1) {
Integer d = div[x];
soinsu.put(d, soinsu.getOrDefault(d, 0) + 1);
x /= d;
}
return soinsu;
}
public boolean isSosuu(int x) {
return div[x] == x;
}
}
/**
* 素因数分解
* @param n
* @return key：素因数、val：指数
*/
static Map<Integer, Integer> bunkai(int n) {
Map<Integer, Integer> soinsu = new HashMap<>();
int end = (int) Math.sqrt(n);
int d = 2;
while (n > 1) {
if (n % d == 0) {
n /= d;
soinsu.put(d, soinsu.getOrDefault(d, 0) + 1);
end = (int) Math.sqrt(n);
} else {
if (d > end) {
d = n - 1;
}
d++;
}
}
return soinsu;
}
/**
* 約数の数
*/
static int getDivCnt(int val) {
Map<Integer, Integer> soinsu = bunkai(val);
int cnt = 1;
for (int key : soinsu.keySet()) {
cnt *= soinsu.get(key) + 1;
}
return cnt;
}
/**
* nの約数リスト（実行時間 n=10^16：約860ms）
*/
static List<Long> divList(long n) {
List<Long> list = new ArrayList<>();
long end = (long) Math.sqrt(n);
for (int i = 1; i <= end; i++) {
if (n % i == 0) {
list.add((long) i);
}
}
int i = end * end == n ? list.size() - 2 : list.size() - 1;
for ( ; i >= 0; i--) {
list.add(n / list.get(i));
}
return list;
}
static List<Integer> divList(int n) {
List<Integer> list = new ArrayList<>();
int end = (int) Math.sqrt(n);
for (int i = 1; i <= end; i++) {
if (n % i == 0) {
list.add(i);
}
}
int i = end * end == n ? list.size() - 2 : list.size() - 1;
for ( ; i >= 0; i--) {
list.add(n / list.get(i));
}
return list;
}
/**
* n以下の素数リスト
* n=10^6・・・実行時間：約110ms 要素数：78498
* n=10^7・・・実行時間：約1700ms 要素数：664579
*/
static List<Integer> sosuuList(int n) {
List<Integer> sosuu = new ArrayList<>();
for (int i = 2; i <= n; i++) {
int r = (int) Math.sqrt(i);
boolean flg = false;
for (Integer o : sosuu) {
if (r < o) {
break;
}
if (i % o == 0) {
flg = true;
break;
}
}
if (!flg) {
sosuu.add(i);
}
}
return sosuu;
}
/**
* 素数判定
*/
static boolean isSosuu(long n) {
if (n < 2) return false;
if (n == 2) return true;
long end = (int) Math.sqrt(n) + 1;
for (int i = 2; i <= end; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
/**
* 最大公約数
*/
static long gcd(long a, long b) {
return b == 0 ? a : gcd(b, a % b);
}
/**
* 最小公倍数
*/
static long lcm(long a, long b) {
BigInteger ba = BigInteger.valueOf(a);
BigInteger bb = BigInteger.valueOf(b);
return ba.multiply(bb).divide(ba.gcd(bb)).longValue();
}
/**
* a / b mod m
*/
static long divide(long a, long b, int m) {
BigInteger ba = BigInteger.valueOf(a);
BigInteger bm = BigInteger.valueOf(m);
BigInteger bb = BigInteger.valueOf(b).modInverse(bm);
return ba.multiply(bb).mod(bm).longValue();
}
/**
* xのn乗根（x≦10^18、n≧60だと1）
*/
static int root(long x, int n) {
int ng = 1000000001;
int ok = 1;
while (ng - ok > 1) {
int mid = (ok + ng) / 2;
if (Math.pow(mid, n) <= Long.MAX_VALUE) {
ok = mid;
} else {
ng = mid;
}
}
ng = ok + 1;
ok = 1;
while (ng - ok > 1) {
int mid = (ok + ng) / 2;
if (power(mid, n) <= x) {
ok = mid;
} else {
ng = mid;
}
}
return ok;
}
/**
* xのn乗
*/
static long power(long x, long n) {
if (n == 0) {
return 1;
}
long val = power(x, n / 2);
val = val * val;
if (n % 2 == 1) {
val = val * x;
}
return val;
}
/**
* xのn乗をmで割った余り
*/
static long power(long x, long n, int m) {
if (n == 0) {
return 1;
}
long val = power(x, n / 2, m);
val = val * val % m;
if (n % 2 == 1) {
val = val * x % m;
}
return val;
}
/**
* 行列累乗 O(N^3logK)
* 行列aのk乗の各要素をmで割った余り
*/
static long[][] matrixPow(long[][] a, long k, int m) {
if (k == 1) {
return a;
}
long[][] ret = matrixPow(a, k / 2, m);
ret = matrixMul(ret, ret, m);
if (k % 2 == 1) {
ret = matrixMul(ret, a, m);
}
return ret;
}
static long[][] matrixMul(long[][] a, long[][] b, int m) {
int n = a.length;
long[][] c = new long[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int x = 0; x < n; x++) {
c[i][j] += a[i][x] * b[x][j];
c[i][j] %= m;
}
}
}
return c;
}
/**
* 行列累乗でフィボナッチ数列
*/
static void matrixPow() {
// 以下のような行列を作ることが多そう
// ? ? ? ? a3
// 1 0 0 0 * a2
// 0 1 0 0 a1
// 0 0 1 0 a0
int k = 2;
int[][][] c = new int[6][k][k];
c[0][0][0] = 1;
c[0][0][1] = 1;
c[0][1][0] = 1;
for (int i = 0; i < c.length - 1; i++) {
for (int j = 0; j < k; j++) {
for (int j2 = 0; j2 < k; j2++) {
for (int x = 0; x < k; x++) {
c[i + 1][j][j2] += c[i][j][x] * c[i][x][j2];
}
}
}
}
// a1～a46を出力
for (int m = 0; m < 45; m++) {
int[] a = {1, 1}; // a1, a0
for (int i = 0; i < c.length; i++) {
if ((m >> i & 1) == 1) {
int[] tmp = new int[k];
for (int j = 0; j < k; j++) {
for (int x = 0; x < k; x++) {
tmp[j] += c[i][j][x] * a[x];
}
}
a = tmp;
}
}
System.out.println(a[0]);
}
// トリボナッチ数列
// https://atcoder.jp/contests/abc006/submissions/12291470
// 足し算をXOR、掛け算をANDにしたケース
// https://atcoder.jp/contests/abc009/submissions/12290718
}
/**
* 二次元配列を左90度回転
*/
static int[][] turnLeft(int[][] a) {
int h = a.length;
int w = a[0].length;
int w1 = w - 1;
int[][] b = new int[w][h];
for (int i = 0; i < w; i++) {
for (int j = 0; j < h; j++) {
b[i][j] = a[j][w1 - i];
}
}
return b;
}
/**
* 二次元配列を右90度回転
*/
static int[][] turnRight(int[][] a) {
int h = a.length;
int w = a[0].length;
int h1 = h - 1;
int[][] b = new int[w][h];
for (int i = 0; i < w; i++) {
for (int j = 0; j < h; j++) {
b[i][j] = a[h1 - j][i];
}
}
return b;
}
/**
* 掃き出し法 O(NlogA)
* 最上位から貪欲に以下のようなものを作る
* ※上から3桁目が1の要素がない場合
* arr[0]：1000・・・ ←msb[0]：62
* arr[1]：0100・・・ ←msb[1]：61
* arr[2]：0001・・・ ←msb[2]：59
* rank：3
*/
static class Hakidasi {
long[] arr;
int[] msb;
int n, rank;
public Hakidasi(long[] a) {
n = a.length;
arr = Arrays.copyOf(a, n);
msb = new int[n];
for (int i = 62; i >= 0; i--) {
boolean flg = false;
for (int j = rank; j < n; j++) {
if ((arr[j] >> i & 1) == 1) {
long t = arr[rank];
arr[rank] = arr[j];
arr[j] = t;
flg = true;
break;
}
}
if (flg) {
msb[rank] = i;
for (int j = 0; j < n; j++) {
if (j != rank && (arr[j] >> i & 1) == 1) {
arr[j] ^= arr[rank];
}
}
rank++;
}
}
}
}
/**
* 値重複可能なHashSet
*/
static class MultiSet<T> {
Map<T, Integer> map = new HashMap<>();
int size = 0;
void add(T e) {
map.put(e, map.getOrDefault(e, 0) + 1);
size++;
}
void remove(T e) {
if (e != null && map.containsKey(e)) {
int val = map.get(e);
if (val == 1) {
map.remove(e);
} else {
map.put(e, val - 1);
}
size--;
}
}
int sizeAll() {
return size;
}
int sizeUnq() {
return map.size();
}
boolean contains(T e) {
return map.containsKey(e);
}
boolean isEmpty() {
return size == 0;
}
@SuppressWarnings("unchecked")
T[] toArrayUnq() {
Object[] arr = map.keySet().toArray();
return (T[]) arr;
}
@SuppressWarnings("unchecked")
T[] toArrayAll() {
Object[] arr = new Object[size];
int idx = 0;
for (T e : map.keySet()) {
int num = map.get(e);
for (int i = 0; i < num; i++) {
arr[idx] = e;
idx++;
}
}
return (T[]) arr;
}
}
/**
* 値重複可能なTreeSet
*/
static class MultiTreeSet<T> {
TreeMap<T, Integer> map = new TreeMap<>();
int size = 0;
void add(T e) {
map.put(e, map.getOrDefault(e, 0) + 1);
size++;
}
void remove(T e) {
if (e != null && map.containsKey(e)) {
int val = map.get(e);
if (val == 1) {
map.remove(e);
} else {
map.put(e, val - 1);
}
size--;
}
}
int sizeAll() {
return size;
}
int sizeUnq() {
return map.size();
}
boolean contains(T e) {
return map.containsKey(e);
}
boolean isEmpty() {
return size == 0;
}
T lower(T e) {
return map.lowerKey(e);
}
T floor(T e) {
return map.floorKey(e);
}
T higher(T e) {
return map.higherKey(e);
}
T ceiling(T e) {
return map.ceilingKey(e);
}
T first() {
return map.firstKey();
}
T last() {
return map.lastKey();
}
T pollFirst() {
T e = map.firstKey();
remove(e);
return e;
}
T pollLast() {
T e = map.lastKey();
remove(e);
return e;
}
@SuppressWarnings("unchecked")
T[] toArrayUnq() {
Object[] arr = map.keySet().toArray();
return (T[]) arr;
}
@SuppressWarnings("unchecked")
T[] toArrayAll() {
Object[] arr = new Object[size];
int idx = 0;
for (T e : map.keySet()) {
int num = map.get(e);
for (int i = 0; i < num; i++) {
arr[idx] = e;
idx++;
}
}
return (T[]) arr;
}
}
/**
* 対象値の件数をカウント（null回避）
* キー：対象値、値：対象値の件数
*/
static void addCntMap(Map<Integer, Integer> map, Integer key) {
map.put(key, map.getOrDefault(key, 0) + 1);
}
static void delCntMap(Map<Integer, Integer> map, Integer key) {
if (key != null && map.containsKey(key)) {
int val = map.get(key);
if (val == 1) {
map.remove(key);
} else {
map.put(key, val - 1);
}
}
}
/**
* UnionFind
*/
static class UnionFind {
int[] parent, size;
int num = 0; // 連結成分の数
UnionFind(int n) {
parent = new int[n];
size = new int[n];
num = n;
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
void union(int x, int y) {
int px = find(x);
int py = find(y);
if (px != py) {
parent[px] = py;
size[py] += size[px];
num--;
}
}
int find(int x) {
if (parent[x] == x) {
return x;
}
parent[x] = find(parent[x]);
return parent[x];
}
/**
* xとyが同一連結成分か
*/
boolean same(int x, int y) {
return find(x) == find(y);
}
/**
* xを含む連結成分のサイズ
*/
int size(int x) {
return size[find(x)];
}
}
// static void union(int[] parent, int[] rank, int x, int y) {
// int px = find(parent, x);
// int py = find(parent, y);
// if (px != py) {
// if (rank[px] < rank[py]) {
// parent[px] = py;
// } else {
// parent[py] = px;
// if (rank[px] == rank[py]) {
// rank[px]++;
// }
// }
// }
// }
/**
* ワーシャルフロイド法 O(N^3)
*/
static void warshallFloyd() {
// i=jは0、辺があればその重み、それ以外は無限大で初期化
int n = 5;
int m = 10;
int inf = 1000000000;
int[][] d = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j) {
d[i][j] = inf;
}
}
}
for (int i = 0; i < m; i++) {
int a = 0;
int b = 1;
int t = 100;
d[a][b] = t;
d[b][a] = t;
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (d[i][k] != inf && d[k][j] != inf) {
d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
}
}
}
}
}
/**
* ベルマンフォード法 O(NM)
*/
static long[] bellmanFord() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] sa = br.readLine().split(" ");
int n = Integer.parseInt(sa[0]);
int m = Integer.parseInt(sa[1]);
int[] a = new int[m];
int[] b = new int[m];
int[] c = new int[m];
for (int i = 0; i < m; i++) {
sa = br.readLine().split(" ");
a[i] = Integer.parseInt(sa[0]) - 1;
b[i] = Integer.parseInt(sa[1]) - 1;
c[i] = Integer.parseInt(sa[2]);
}
br.close();
// 関数化したい場合
// static long[] bellmanFord(int[] a, int[] b, int[] c, int s) {
// int n = a.length;
int s = 0;
long[] d = new long[n];
Arrays.fill(d, 1_000_000_000_000_000_000L);
d[s] = 0;
boolean upd = true;
for (int i = 0; i <= n && upd; i++) {
upd = false;
for (int j = 0; j < m; j++) {
long alt = d[a[j]] + c[j];
if (alt < d[b[j]]) {
d[b[j]] = alt;
upd = true;
}
}
if (i == n) {
// 負閉路時処理
}
}
return d;
}
/**
* ダイクストラ法 O(M + NlogN)
*/
static long[] dijkstra() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] sa = br.readLine().split(" ");
int n = Integer.parseInt(sa[0]);
int m = Integer.parseInt(sa[1]);
List<List<Hen>> list = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
list.add(new ArrayList<>());
}
for (int i = 0; i < m; i++) {
sa = br.readLine().split(" ");
int a = Integer.parseInt(sa[0]) - 1;
int b = Integer.parseInt(sa[1]) - 1;
int c = Integer.parseInt(sa[2]);
list.get(a).add(new Hen(b, c));
list.get(b).add(new Hen(a, c));
}
br.close();
// 関数化したい場合
// static long[] dijkstra(List<List<Hen>> list, int s) {
int s = 0;
long[] d = new long[list.size()];
Arrays.fill(d, Long.MAX_VALUE);
d[s] = 0;
PriorityQueue<Node> que = new PriorityQueue<Node>();
Node first = new Node(s, 0);
que.add(first);
while (!que.isEmpty()) {
Node cur = que.poll();
// 要見直し
// 辺が多すぎる場合、同じcurを二度見ない条件がないとTLEするっぽい
// 全組合せの辺があるなら、NextSetを作り、Curを取り除けたら次を調べる
// PriorityQueueではなくTreeSetを使うなら、removeしてからaddする
// ↓怪しいけど暫定。確定済み配列を持つのが確実か。
if (cur.d > d[cur.v]) {
continue;
}
for (Hen hen : list.get(cur.v)) {
long alt = d[cur.v] + hen.c;
if (alt < d[hen.v]) {
d[hen.v] = alt;
que.add(new Node(hen.v, alt));
}
}
}
return d;
}
static class Hen {
int v, c;
public Hen(int v, int c) {
this.v = v;
this.c = c;
}
}
static class Node implements Comparable<Node> {
int v;
long d;
public Node(int v, long d) {
this.v = v;
this.d = d;
}
public int compareTo(Node o) {
return Long.compare(d, o.d);
}
}
/**
* トポロジカルソート O(N + M)
*/
static List<Integer> topologicalSort() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] sa = br.readLine().split(" ");
int n = Integer.parseInt(sa[0]);
int m = Integer.parseInt(sa[1]);
List<List<Integer>> list = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
list.add(new ArrayList<>());
}
int[] inCnt = new int[n];
for (int i = 0; i < m; i++) {
sa = br.readLine().split(" ");
int a = Integer.parseInt(sa[0]) - 1;
int b = Integer.parseInt(sa[1]) - 1;
list.get(a).add(b);
inCnt[b]++;
}
br.close();
List<Integer> res = new ArrayList<>(n);
Queue<Integer> que = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
if (inCnt[i] == 0) {
que.add(i);
}
}
while (!que.isEmpty()) {
int cur = que.poll();
res.add(cur);
for (int i : list.get(cur)) {
inCnt[i]--;
if (inCnt[i] == 0) {
que.add(i);
}
}
}
return res;
}
/**
* 二部グラフの構築（Node2.grpに1か2を設定する）
*/
static Node2[] nibuGraph() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] sa = br.readLine().split(" ");
int n = Integer.parseInt(sa[0]);
int m = Integer.parseInt(sa[1]);
Node2[] arr = new Node2[n];
for (int i = 0; i < n; i++) {
Node2 o = new Node2();
arr[i] = o;
}
for (int i = 0; i < m; i++) {
sa = br.readLine().split(" ");
int a = Integer.parseInt(sa[0]) - 1;
int b = Integer.parseInt(sa[1]) - 1;
arr[a].nexts.add(b);
arr[b].nexts.add(a);
}
br.close();
Queue<Integer> que = new ArrayDeque<>();
que.add(0);
arr[0].grp = 1;
while (!que.isEmpty()) {
int cur = que.poll();
for (int next : arr[cur].nexts) {
if (arr[next].grp == 0) {
que.add(next);
arr[next].grp = 3 - arr[cur].grp;
} else if (arr[next].grp == arr[cur].grp) {
// 二部グラフではない
}
}
}
// 最大マッチング
int cntmatch = 0;
for (int i = 0; i < n; i++) {
if (arr[i].grp == 1 && arr[i].target == null && matching(arr, new HashSet<>(), i)) {
cntmatch++;
}
}
System.out.println(cntmatch);
return arr;
}
/**
* （二部グラフの最大マッチング）増加路の探索、マッチング更新
*/
static boolean matching(Node2[] arr, Set<Integer> used, int cur) {
Node2 o = arr[cur];
for (int next : o.nexts) {
if (!used.contains(next)) {
used.add(next);
if (arr[next].target == null || matching(arr, used, arr[next].target)) {
arr[next].target = cur;
arr[cur].target = next;
return true;
}
}
}
return false;
}
static class Node2 {
int grp;
Integer target;
List<Integer> nexts = new ArrayList<>();
}
/**
* 最大流、最小カット（フォード・ファルカーソンのアルゴリズム） O(E・maxflow)
*/
static class MaxFlow {
int n;
List<List<Hen>> list;
boolean[] visit;
public MaxFlow(int n) {
this.n = n;
list = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
list.add(new ArrayList<>());
}
visit = new boolean[n];
}
void addHen(int u, int v, int cap) {
list.get(u).add(new Hen(v, list.get(v).size(), cap));
list.get(v).add(new Hen(u, list.get(u).size() - 1, cap));
}
int calc(int start, int goal) {
int ret = 0;
while (true) {
Arrays.fill(visit, false);
int used = dfs(start, goal, Integer.MAX_VALUE);
if (used == 0) {
return ret;
}
ret += used;
}
}
private int dfs(int cur, int goal, int src) {
if (cur == goal) {
return src;
}
visit[cur] = true;
for (Hen h : list.get(cur)) {
if (!visit[h.v] && h.cap > 0) {
int used = dfs(h.v, goal, Math.min(src, h.cap));
if (used > 0) {
h.cap -= used;
list.get(h.v).get(h.vi).cap += used;
return used;
}
}
}
return 0;
}
private class Hen {
int v, vi, cap;
public Hen(int v, int vi, int cap) {
this.v = v;
this.vi = vi;
this.cap = cap;
}
}
}
static void rerooting2() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] sa = br.readLine().split(" ");
int n = Integer.parseInt(sa[0]);
int m = Integer.parseInt(sa[1]);
int[][] edges = new int[n - 1][2];
for (int i = 0; i < edges.length; i++) {
sa = br.readLine().split(" ");
edges[i][0] = Integer.parseInt(sa[0]) - 1;
edges[i][1] = Integer.parseInt(sa[1]) - 1;
}
br.close();
Rerooting2<Long> r = new Rerooting2<>(n, edges, 1L,
(o1, o2) -> {
return o1 * o2 % m;
},
(o, i) -> {
return o + 1;
});
PrintWriter pw = new PrintWriter(System.out);
for (int i = 0; i < n; i++) {
pw.println(r.query(i) - 1);
}
pw.flush();
}
/**
* 全方位木DP
*/
static class Rerooting2<T> {
public int nodeCnt;
private T identity;
private BiFunction<T, T, T> merge;
private BiFunction<T, Integer, T> addNode;
private List<List<Integer>> adjacents;
private List<List<Integer>> indexForAdjacent;
private Object[][] dp;
private Object[] res;
/**
* 初期化
* @param nodeCnt 頂点数（≧1）
* @param edges 木構造の辺の配列 例：{{0,1},{0,2},{1,3}}
* @param identity 単位元
* @param merge 部分木のマージ関数（戻り値は新規オブジェクト）
* @param addNode 指定頂点（部分木の根）の分を加算する関数（戻り値は新規オブジェクト）
*/
public Rerooting2(int nodeCnt, int[][] edges, T identity,
BiFunction<T, T, T> merge, BiFunction<T, Integer, T> addNode) {
this.nodeCnt = nodeCnt;
this.identity = identity;
this.merge = merge;
this.addNode = addNode;
adjacents = new ArrayList<>(nodeCnt);
indexForAdjacent = new ArrayList<>(nodeCnt);
for (int i = 0; i < nodeCnt; i++) {
adjacents.add(new ArrayList<>());
indexForAdjacent.add(new ArrayList<>());
}
for (int i = 0; i < edges.length; i++) {
int[] edge = edges[i];
indexForAdjacent.get(edge[0]).add(adjacents.get(edge[1]).size());
indexForAdjacent.get(edge[1]).add(adjacents.get(edge[0]).size());
adjacents.get(edge[0]).add(edge[1]);
adjacents.get(edge[1]).add(edge[0]);
}
dp = new Object[nodeCnt][];
res = new Object[nodeCnt];
for (int i = 0; i < nodeCnt; i++) {
dp[i] = new Object[adjacents.get(i).size()];
}
if (nodeCnt == 1) {
res[0] = addNode.apply(identity, 0);
} else {
initialize();
}
}
@SuppressWarnings("unchecked")
public T query(int node) {
return (T) res[node];
}
@SuppressWarnings("unchecked")
private void initialize() {
int[] parents = new int[nodeCnt];
int[] order = new int[nodeCnt];
// InitOrderedTree
int index = 0;
Deque<Integer> stack = new ArrayDeque<>();
stack.addFirst(0);
parents[0] = -1;
while (!stack.isEmpty()) {
int current = stack.pollFirst();
order[index++] = current;
for (int adjacent : adjacents.get(current)) {
if (adjacent == parents[current]) continue;
stack.addFirst(adjacent);
parents[adjacent] = current;
}
}
// FromLeaf
for (int i = order.length - 1; i >= 1; i--) {
int node = order[i];
int parent = parents[node];
T accum = identity;
int parentIndex = -1;
for (int j = 0; j < adjacents.get(node).size(); j++) {
if (adjacents.get(node).get(j) == parent) {
parentIndex = j;
continue;
}
accum = merge.apply(accum, (T) dp[node][j]);
}
dp[parent][indexForAdjacent.get(node).get(parentIndex)] = addNode.apply(accum, node);
}
// ToLeaf
for (int node : order) {
T accum = identity;
Object[] accumsFromTail = new Object[adjacents.get(node).size()];
accumsFromTail[accumsFromTail.length - 1] = identity;
for (int j = accumsFromTail.length - 1; j >= 1; j--) {
accumsFromTail[j - 1] = merge.apply((T) dp[node][j], (T) accumsFromTail[j]);
}
for (int j = 0; j < accumsFromTail.length; j++) {
dp[adjacents.get(node).get(j)][indexForAdjacent.get(node).get(j)] =
addNode.apply(merge.apply(accum, (T) accumsFromTail[j]), node);
accum = merge.apply(accum, (T) dp[node][j]);
}
res[node] = addNode.apply(accum, node);
}
}
}
static void rerooting3() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] sa = br.readLine().split(" ");
int n = Integer.parseInt(sa[0]);
int m = Integer.parseInt(sa[1]);
int[][] edges = new int[n - 1][2];
for (int i = 0; i < edges.length; i++) {
sa = br.readLine().split(" ");
edges[i][0] = Integer.parseInt(sa[0]) - 1;
edges[i][1] = Integer.parseInt(sa[1]) - 1;
}
br.close();
Rerooting3<Long> r = new Rerooting3<>(n, edges, 1L,
(o, i) -> {
return o + 1;
},
(o1, o2) -> {
return o1 * o2 % m;
},
(o, i) -> {
return o;
});
// Rerooting3<Obj> r = new Rerooting3<>(n, edges, new Obj(),
// (o, i) -> {
// return o;
// },
// (o1, o2) -> {
// Obj ret = new Obj();
// ret.max = Math.max(o1.isAcm ? o1.max : o1.size, o2.isAcm ? o2.max : o2.size);
// ret.size = o1.size + o2.size;
// ret.isAcm = true;
// return ret;
// },
// (o, i) -> {
// Obj ret = new Obj();
// ret.max = o.max;
// ret.size = o.size + 1;
// return ret;
// });
PrintWriter pw = new PrintWriter(System.out);
for (int i = 0; i < n; i++) {
pw.println(r.query(i));
}
for (int i = 0; i < n; i++) {
int max = 0;
for (int j = 0; j < r.dp[i].length; j++) {
max = Math.max(max, (int) r.dp[i][j]);
}
pw.println(max);
}
pw.flush();
}
/**
* 全方位木DP
*/
static class Rerooting3<T> {
public int nodeCnt;
private T identity;
private BiFunction<T, Integer, T> beforeMerge;
private BiFunction<T, T, T> merge;
private BiFunction<T, Integer, T> afterMerge;
private List<List<Integer>> adjacents;
private List<List<Integer>> indexForAdjacent;
private Object[][] dp;
private Object[] res;
/**
* 初期化
* @param nodeCnt 頂点数（≧1）
* @param edges 木構造の辺の配列 例：{{0,1},{0,2},{1,3}}
* @param identity 単位元
* @param beforeMerge 指定頂点（部分木の子）を計算する関数（何もしない場合以外戻り値は新規オブジェクト）
* @param merge 部分木のマージ関数（戻り値は新規オブジェクト）
* @param afterMerge 指定頂点（部分木の根）の分を計算する関数（何もしない場合以外戻り値は新規オブジェクト）
*/
public Rerooting3(int nodeCnt, int[][] edges, T identity, BiFunction<T, Integer, T> beforeMerge,
BiFunction<T, T, T> merge, BiFunction<T, Integer, T> afterMerge) {
this.nodeCnt = nodeCnt;
this.identity = identity;
this.beforeMerge = beforeMerge;
this.merge = merge;
this.afterMerge = afterMerge;
adjacents = new ArrayList<>(nodeCnt);
indexForAdjacent = new ArrayList<>(nodeCnt);
for (int i = 0; i < nodeCnt; i++) {
adjacents.add(new ArrayList<>());
indexForAdjacent.add(new ArrayList<>());
}
for (int i = 0; i < edges.length; i++) {
int[] edge = edges[i];
indexForAdjacent.get(edge[0]).add(adjacents.get(edge[1]).size());
indexForAdjacent.get(edge[1]).add(adjacents.get(edge[0]).size());
adjacents.get(edge[0]).add(edge[1]);
adjacents.get(edge[1]).add(edge[0]);
}
dp = new Object[nodeCnt][];
res = new Object[nodeCnt];
for (int i = 0; i < nodeCnt; i++) {
dp[i] = new Object[adjacents.get(i).size()];
}
if (nodeCnt == 1) {
res[0] = afterMerge.apply(identity, 0);
} else {
initialize();
}
}
@SuppressWarnings("unchecked")
public T query(int node) {
return (T) res[node];
}
@SuppressWarnings("unchecked")
private void initialize() {
int[] parents = new int[nodeCnt];
int[] order = new int[nodeCnt];
// InitOrderedTree
int index = 0;
Deque<Integer> stack = new ArrayDeque<>();
stack.addFirst(0);
parents[0] = -1;
while (!stack.isEmpty()) {
int current = stack.pollFirst();
order[index++] = current;
for (int adjacent : adjacents.get(current)) {
if (adjacent == parents[current]) continue;
stack.addFirst(adjacent);
parents[adjacent] = current;
}
}
// FromLeaf
for (int i = order.length - 1; i >= 1; i--) {
int node = order[i];
int parent = parents[node];
T accum = identity;
int parentIndex = -1;
for (int j = 0; j < adjacents.get(node).size(); j++) {
if (adjacents.get(node).get(j) == parent) {
parentIndex = j;
continue;
}
accum = merge.apply(accum, beforeMerge.apply((T) dp[node][j], adjacents.get(node).get(j)));
}
dp[parent][indexForAdjacent.get(node).get(parentIndex)] = afterMerge.apply(accum, node);
}
// ToLeaf
for (int node : order) {
T accum = identity;
Object[] accumsFromTail = new Object[adjacents.get(node).size()];
accumsFromTail[accumsFromTail.length - 1] = identity;
for (int j = accumsFromTail.length - 1; j >= 1; j--) {
accumsFromTail[j - 1] = merge.apply(
(T) accumsFromTail[j],
beforeMerge.apply((T) dp[node][j], adjacents.get(node).get(j)));
}
for (int j = 0; j < accumsFromTail.length; j++) {
dp[adjacents.get(node).get(j)][indexForAdjacent.get(node).get(j)] =
afterMerge.apply(merge.apply(accum, (T) accumsFromTail[j]), node);
accum = merge.apply(accum, beforeMerge.apply((T) dp[node][j], adjacents.get(node).get(j)));
}
res[node] = afterMerge.apply(accum, node);
}
}
}
/**
* 強連結成分分解
*/
static class StrongBunkai {
private List<List<Integer>> list1, list2;
private boolean[] visit;
private List<Integer> order;
public int cnt = 0; // 強連結成分の数
public int[] grp; // グループ（配列の要素数：n、値：0～cnt-1）
public int[] size; // グループ（0～cnt-1）の頂点数
public List<Set<Integer>> list; // 強連結成分間のみの隣接リスト
/**
* 初期化
* @param n 頂点数
* @param list1 隣接リスト
* @param list2 逆辺の隣接リスト
*/
public StrongBunkai(int n, List<List<Integer>> list1, List<List<Integer>> list2) {
this.list1 = list1;
this.list2 = list2;
visit = new boolean[n];
order = new ArrayList<>(n);
grp = new int[n];
Arrays.fill(grp, -1);
for (int i = 0; i < n; i++) {
dfs(i);
}
Collections.reverse(order);
for (int i : order) {
if (grp[i] == -1) {
dfsr(i);
cnt++;
}
}
size = new int[cnt];
list = new ArrayList<>(cnt);
for (int i = 0; i < cnt; i++) {
list.add(new HashSet<>());
}
for (int i = 0; i < n; i++) {
size[grp[i]]++;
for (int j : list1.get(i)) {
if (grp[i] != grp[j]) {
list.get(grp[i]).add(grp[j]);
}
}
}
}
private void dfs(int x) {
if (visit[x]) {
return;
}
visit[x] = true;
for (int y : list1.get(x)) {
dfs(y);
}
order.add(x);
}
private void dfsr(int x) {
grp[x] = cnt;
for (int y : list2.get(x)) {
if (grp[y] == -1) {
dfsr(y);
}
}
}
}
/**
* 幅優先探索
*/
static void bfs() {
Queue<Integer> que = new ArrayDeque<>();
que.add(0);
// firstに訪問済みの印を付ける
while (!que.isEmpty()) {
Integer cur = que.poll();
// ↓次に遷移可能な数分ループ
for (int i = 0; i < 4; i++) {
// ↓未訪問の場合
if (cur == null) {
que.add(i);
// nextに訪問済みの印を付ける
}
}
}
}
/**
* 配列要素の順列の全列挙（N=10で実行時間約500ms）
* setは配列のインデックスを格納するワーク変数
* permutation(target, new LinkedHashSet<>());
*/
static void permutation(int[] target, LinkedHashSet<Integer> set) {
if (set.size() == target.length) {
// for (int i : set) {
// // target[i]に関する処理
// }
return;
}
for (int i = 0; i < target.length; i++) {
if (!set.contains(i)) {
set.add(i);
permutation(target, set);
set.remove(i);
}
}
}
/**
* 配列からk個の要素を取る組み合わせの全列挙
* listは配列のインデックスを格納するワーク変数
* combination(target, k, new ArrayList<Integer>());
*/
static void combination(int[] target, int k, List<Integer> list) {
if (list.size() == k) {
// for (int i : list) {
// // target[i]に関する処理
// }
return;
}
int i = 0;
if (!list.isEmpty()) {
i = list.get(list.size() - 1) + 1;
if (list.size() + target.length - i < k) {
return;
}
}
for ( ; i < target.length; i++) {
list.add(i);
combination(target, k, list);
list.remove(list.size() - 1);
}
}
/**
* 順列を辞書順で1つ進める O(NlogN)
* 降順ソートされている場合はnull
* ※前提：N≧2、要素が相異なる
*/
static int[] nextPermutation(int[] a) {
TreeSet<Integer> set = new TreeSet<>();
set.add(a[a.length - 1]);
for (int i = a.length - 2; i >= 0; i--) {
if (a[i] > a[i + 1] || set.higher(a[i]) == null) {
set.add(a[i]);
} else {
int[] b = new int[a.length];
for (int j = 0; j < i; j++) {
b[j] = a[j];
}
b[i] = set.higher(a[i]);
set.remove(b[i]);
set.add(a[i]);
Integer[] arr = set.toArray(new Integer[0]);
for (int j = 0; j < arr.length; j++) {
b[i + 1 + j] = arr[j];
}
return b;
}
}
return null;
}
/**
* 最長増加部分列（Longest Increasing Subsequence）※狭義単調増加
* @return 列の長さ
*/
static int lis() {
int n = 5;
int[] a = {1, 4, 2, 3, 5};
// 長さiの部分列の最後の数値として最小のものを持つ配列
int[] val = new int[n + 1];
for (int i = 1; i <= n; i++) {
val[i] = Integer.MAX_VALUE;
}
for (int i = 0; i < n; i++) {
int idx = Arrays.binarySearch(val, a[i]);
// // 広義単調増加の場合
// int idx = Arrays.binarySearch(val, a[i] + 1);
if (idx < 0) idx = ~idx;
val[idx] = a[i];
}
int lis = Arrays.binarySearch(val, Integer.MAX_VALUE - 1);
if (lis < 0) {
lis = ~lis;
lis--;
}
return lis;
}
/**
* 最長共通部分列
*/
static char[] lcs(char[] s, char[] t) {
int a = s.length;
int b = t.length;
int[][] dp = new int[a + 1][b + 1];
for (int i = 1; i <= a; i++) {
for (int j = 1; j <= b; j++) {
if (s[i - 1] == t[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
char[] lcs = new char[dp[a][b]];
while (a > 0 && b > 0) {
if (dp[a][b] == dp[a - 1][b]) {
a--;
} else if (dp[a][b] == dp[a][b - 1]) {
b--;
} else {
a--;
b--;
lcs[dp[a][b]] = s[a];
}
}
return lcs;
}
/**
* MP法
* arr2にarr1が出現するインデックス（0～|arr2|-|arr1|）を全て取得
* arrをint→charにすれば文字列にも使えるはず・・
*/
static class MP {
int n;
int[] arr;
int[] a;
public MP(int[] arr1) {
arr = arr1;
n = arr.length;
a = new int[n + 1];
a[0] = -1;
int j = -1;
for (int i = 0; i < n; i++) {
while (j >= 0 && arr[i] != arr[j]) {
j = a[j];
}
j++;
a[i + 1] = j;
}
}
List<Integer> findAllFrom(int[] arr2) {
List<Integer> ret = new ArrayList<>();
int j = 0;
for (int i = 0; i < arr2.length; i++) {
while (j >= 0 && arr2[i] != arr[j]) {
j = a[j];
}
j++;
if (j == n) {
ret.add(i - j + 1);
j = a[j];
}
}
return ret;
}
}
/**
* ナップサック問題（選択したものSetに復元）
*/
static void knapsack() {
// https://atcoder.jp/contests/abc145/submissions/8501047
}
/**
* 座標圧縮
* {2, -1, 5, -3} → {3, 2, 4, 1}
*/
static int[] zaatu(long[] a) {
TreeMap<Long, Integer> map = new TreeMap<>();
for (int i = 0; i < a.length; i++) {
map.put(a[i], null);
}
Long[] arr = map.keySet().toArray(new Long[0]);
int cnt = 0;
for (Long i : arr) {
cnt++;
map.put(i, cnt);
}
int[] b = new int[a.length];
for (int i = 0; i < a.length; i++) {
b[i] = map.get(a[i]);
}
return b;
}
/**
* 高速ゼータ変換 O(N・2^N)
*/
static void fastZetaHenkan() {
int n = 20;
int n2 = 1 << n;
int[] dp = new int[n2];
for (int j = 0; j < n; j++) {
for (int i = 0; i < n2; i++) {
if ((i >> j & 1) == 1) {
dp[i] += dp[i & ~(1 << j)];
}
}
}
}
/**
* トライ木
*/
static void trie() {
// https://atcoder.jp/contests/agc047/submissions/15830815
}
/**
* 転倒数
* 0＜a[i]であれば前半は不要
* a[i]が大きいなら要座圧
*/
static long tentousuu(int[] a) {
int n = a.length;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
min = Math.min(min, a[i]);
max = Math.max(max, a[i]);
}
min--;
int[] b = new int[n];
for (int i = 0; i < n; i++) {
b[i] = a[i] - min;
}
BIT bit = new BIT(max - min);
long ret = 0;
for (int i = 0; i < n; i++) {
ret += i - bit.sum(b[i]);
bit.add(b[i], 1);
}
return ret;
}
/**
* Binary Indexed Tree
* 要素数nで初期化
* add、sumは1-indexed
*/
static class BIT {
int n;
long[] arr;
public BIT(int n) {
this.n = n;
arr = new long[n + 1];
}
void add(int idx, long val) {
for (int i = idx; i <= n; i += i & -i) {
arr[i] += val;
}
}
long sum(int idx) {
long sum = 0;
for (int i = idx; i > 0; i -= i & -i) {
sum += arr[i];
}
return sum;
}
}
/**
* セグ木で最小共通祖先（Lowest Common Ancestor）
*/
static class SegTreeLCA {
int n = 2;
int n2, idx;
Node[] arr;
int[] first;
Node INF = new Node(-1, Integer.MAX_VALUE);
/**
* 初期化
* @param size 頂点数
* @param list 隣接リスト
* @param root 根の頂点番号
*/
public SegTreeLCA(int size, List<List<Integer>> list, int root) {
while (n < size) {
n <<= 1;
}
n <<= 1;
n2 = n * 2 - 1;
idx = n - 1;
arr = new Node[n2];
first = new int[size];
Arrays.fill(first, -1);
Node r = new Node(root, 0);
arr[idx] = r;
first[root] = idx - n + 1;
idx++;
dfs(list, r, -1);
for (int i = idx; i < n2; i++) {
arr[i] = INF;
}
for (int i = n - 2; i >= 0; i--) {
if (arr[i * 2 + 1].dep < arr[i * 2 + 2].dep) {
arr[i] = arr[i * 2 + 1];
} else {
arr[i] = arr[i * 2 + 2];
}
}
}
private void dfs(List<List<Integer>> list, Node cur, int p) {
for (int c : list.get(cur.i)) {
if (c != p) {
Node o = new Node(c, cur.dep + 1);
arr[idx] = o;
if (first[c] == -1) {
first[c] = idx - n + 1;
}
idx++;
dfs(list, o, cur.i);
arr[idx] = cur;
idx++;
}
}
}
/**
* 頂点Iのオブジェクト取得（0≦I＜size）
*/
public Node get(int i) {
return arr[first[i] + n - 1];
}
/**
* 頂点A,BのLCA取得（0≦A,B＜size）
*/
public Node lca(int a, int b) {
int l = Math.min(first[a], first[b]);
int r = Math.max(first[a], first[b]);
return query(l, r + 1, 0, 0, n);
}
private Node query(int l, int r, int k, int beg, int end) {
if (end <= l || r <= beg) return INF; // 交差しない
if (l <= beg && end <= r) return arr[k]; // 完全に含む
Node o1 = query(l, r, k * 2 + 1, beg, (beg + end) / 2);
Node o2 = query(l, r, k * 2 + 2, (beg + end) / 2, end);
if (o1.dep < o2.dep) {
return o1;
}
return o2;
}
private static class Node {
int i, dep;
public Node(int i, int dep) {
this.i = i;
this.dep = dep;
}
}
}
/**
* ダブリングで最小共通祖先（Lowest Common Ancestor）
*/
static class DoublingLCA {
int n, h = 1, root;
List<List<Integer>> list;
Node[] nodes;
int[][] parent;
/**
* 初期化
* @param list 隣接リスト
* @param root 根の頂点番号
*/
public DoublingLCA(List<List<Integer>> list, int root) {
n = list.size();
this.root = root;
this.list = list;
while ((1 << h) < n) {
h++;
}
nodes = new Node[n];
for (int i = 0; i < n; i++) {
nodes[i] = new Node(i, -1);
}
parent = new int[h][n];
for (int i = 0; i < h; i++) {
Arrays.fill(parent[i], -1);
}
dfs(root, -1, 0);
for (int i = 0; i < h - 1; i++) {
for (int j = 0; j < n; j++) {
if (parent[i][j] != -1) {
parent[i + 1][j] = parent[i][parent[i][j]];
}
}
}
}
private void dfs(int x, int p, int dep) {
parent[0][x] = p;
nodes[x].dep = dep;
for (int next : list.get(x)) {
if (next != p) {
dfs(next, x, dep + 1);
}
}
}
/**
* 頂点A,BのLCA取得（0≦A,B＜N）
*/
public Node lca(int a, int b) {
int u = a;
int v = b;
if (nodes[u].dep < nodes[v].dep) {
u = b;
v = a;
}
for (int i = 0; i < h; i++) {
if ((nodes[u].dep - nodes[v].dep >> i & 1) == 1) {
u = parent[i][u];
}
}
if (u == v) {
return nodes[u];
}
for (int i = h - 1; i >= 0; i--) {
if (parent[i][u] != parent[i][v]) {
u = parent[i][u];
v = parent[i][v];
}
}
return nodes[parent[0][u]];
}
public static class Node {
int i, dep;
public Node(int i, int dep) {
this.i = i;
this.dep = dep;
}
}
}
static void doublingTree() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] sa = br.readLine().split(" ");
int n = Integer.parseInt(sa[0]);
List<List<DoublingTree.Hen>> list = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
list.add(new ArrayList<>());
}
for (int i = 0; i < n - 1; i++) {
sa = br.readLine().split(" ");
int a = Integer.parseInt(sa[0]) - 1;
int b = Integer.parseInt(sa[1]) - 1;
int c = Integer.parseInt(sa[2]);
DoublingTree.Hen h = new DoublingTree.Hen(i, a, b, c);
list.get(h.u).add(h);
list.get(h.v).add(h);
}
br.close();
DoublingTree dt = new DoublingTree(list, 0);
System.out.println(dt.maxCost(0, 1));
}
/**
* ダブリング（木上クエリ処理用）
*/
static class DoublingTree {
int n, h = 1, root;
List<List<Hen>> list;
Node[] nodes;
int[][] parent;
int[][] maxCost;
public DoublingTree(List<List<Hen>> list, int root) {
n = list.size();
this.root = root;
this.list = list;
while ((1 << h) < n) {
h++;
}
nodes = new Node[n];
for (int i = 0; i < n; i++) {
nodes[i] = new Node(i, -1);
}
parent = new int[h][n];
for (int i = 0; i < h; i++) {
Arrays.fill(parent[i], -1);
}
maxCost = new int[h][n];
dfs(root, -1, 0);
for (int i = 0; i < h - 1; i++) {
for (int j = 0; j < n; j++) {
if (parent[i][j] != -1) {
parent[i + 1][j] = parent[i][parent[i][j]];
maxCost[i + 1][j] = Math.max(maxCost[i][j], maxCost[i][parent[i][j]]);
} else {
maxCost[i + 1][j] = maxCost[i][j];
}
}
}
}
private void dfs(int x, int p, int dep) {
parent[0][x] = p;
nodes[x].dep = dep;
for (Hen h : list.get(x)) {
int next = h.u;
if (next == x) {
next = h.v;
}
if (next != p) {
dfs(next, x, dep + 1);
} else {
maxCost[0][x] = h.cost;
}
}
}
// public Node lca(int a, int b) {
// int u = a;
// int v = b;
// if (nodes[u].dep < nodes[v].dep) {
// u = b;
// v = a;
// }
// for (int i = 0; i < h; i++) {
// if ((nodes[u].dep - nodes[v].dep >> i & 1) == 1) {
// u = parent[i][u];
// }
// }
// if (u == v) {
// return nodes[u];
// }
// for (int i = h - 1; i >= 0; i--) {
// if (parent[i][u] != parent[i][v]) {
// u = parent[i][u];
// v = parent[i][v];
// }
// }
// return nodes[parent[0][u]];
// }
/**
* 頂点A,B間の辺の最大コストを取得（0≦A,B＜size）
*/
public int maxCost(int a, int b) {
int u = a;
int v = b;
if (nodes[u].dep < nodes[v].dep) {
u = b;
v = a;
}
int ret = 0;
for (int i = 0; i < h; i++) {
if ((nodes[u].dep - nodes[v].dep >> i & 1) == 1) {
ret = Math.max(ret, maxCost[i][u]);
u = parent[i][u];
}
}
if (u == v) {
return ret;
}
for (int i = h - 1; i >= 0; i--) {
if (parent[i][u] != parent[i][v]) {
ret = Math.max(ret, maxCost[i][u]);
ret = Math.max(ret, maxCost[i][v]);
u = parent[i][u];
v = parent[i][v];
}
}
ret = Math.max(ret, maxCost[0][u]);
ret = Math.max(ret, maxCost[0][v]);
return ret;
}
public static class Node {
int i, dep;
public Node(int i, int dep) {
this.i = i;
this.dep = dep;
}
}
public static class Hen {
int i, u, v, cost;
long ans;
public Hen(int i, int u, int v, int cost) {
this.i = i;
this.u = u;
this.v = v;
this.cost = cost;
}
}
}
/**
* セグ木
* ■最大
* SegTree<Integer> st = new SegTree<>(n, 0, (v1, v2) -> Math.max(v1, v2));
* ■最小
* SegTree<Integer> st = new SegTree<>(n, Integer.MAX_VALUE, (v1, v2) -> Math.min(v1, v2));
* ■和
* SegTree<Integer> st = new SegTree<>(n, 0, (v1, v2) -> v1 + v2);
*/
static class SegTree<T> {
// 親へのアクセス：(n - 1) / 2
// 子へのアクセス：n * 2 + 1、n * 2 + 2
int n = 2; // 要素（葉）の数
int n2; // 全ノード数
T NA;
List<T> list;
BiFunction<T, T, T> func;
/**
* 初期化 O(N)
* @param num 要素（葉）の数
* @param na 単位元
* @param func 区間に対する操作が可能な関数（戻り値は新規オブジェクト）
*/
public SegTree(int num, T na, BiFunction<T, T, T> func) {
while (n < num) n <<= 1;
n2 = n * 2 - 1;
NA = na;
list = new ArrayList<T>(n2);
for (int i = 0; i < n2; i++) list.add(NA);
this.func = func;
}
/**
* 更新 O(logN)
* @param i インデックス（0～n-1）
* @param x 更新値
*/
void update(int i, T x) {
i += n - 1; // arr上でのインデックス
list.set(i, x);
while (i > 0) {
i = (i - 1) / 2;
list.set(i, func.apply(list.get(i * 2 + 1), list.get(i * 2 + 2)));
}
}
/**
* 取得 O(logN)
* インデックスl以上r未満の区間の値
*/
T query(int l, int r) {
return query(l, r, 0, 0, n);
}
/**
* 取得 O(logN)
* インデックスl以上r未満の区間の値、beg, endにはノードkに対応する区間
* query(l, r, 0, 0, n);
*/
private T query(int l, int r, int k, int beg, int end) {
if (end <= l || r <= beg) return NA; // 交差しない
if (l <= beg && end <= r) return list.get(k); // 完全に含む
T v1 = query(l, r, k * 2 + 1, beg, (beg + end) / 2);
T v2 = query(l, r, k * 2 + 2, (beg + end) / 2, end);
return func.apply(v1, v2);
}
}
}