Submission #968666
Source Code Expand
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class Main {
static InputStream is;
static PrintWriter out;
static String INPUT = "";
static void solve()
{
int n = ni(), X = ni();
if(n <= 3){
int[][] g = new int[n][n];
for(int i = 0;i < n;i++){
Arrays.fill(g[i], X);
g[i][i] = 0;
}
for(int i = 0;i < n-1;i++){
int f = ni()-1;
int t = ni()-1;
g[f][t] = g[t][f] = ni();
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (g[i][j] > g[i][k] + g[k][j]) {
g[i][j] = g[i][k] + g[k][j];
}
}
}
}
long ret = 0;
for(int i = 0;i < n;i++){
for(int j = i+1;j < n;j++){
ret += g[i][j];
}
}
out.println(ret);
return;
}
int[] from = new int[n-1];
int[] to = new int[n-1];
int[] w = new int[n-1];
for(int i = 0;i < n-1;i++){
from[i] = ni()-1;
to[i] = ni()-1;
w[i] = ni();
}
int[][][] g = packWU(n, from, to, w);
for(int i = 0;i < n;i++){
for(int[] e : g[i]){
if(g[i].length + g[e[0]].length < n){
e[1] = Math.min(e[1], 2*X);
}
}
}
int[] neimin = new int[n];
Arrays.fill(neimin, Integer.MAX_VALUE / 2);
for(int i = 0;i < n;i++){
for(int[] e : g[i]){
neimin[i] = Math.min(neimin[i], e[1]);
}
}
for(int i = 0;i < n;i++){
for(int[] e : g[i]){
e[1] = Math.min(e[1], neimin[i] + X);
e[1] = Math.min(e[1], neimin[e[0]] + X);
}
}
int[][] pars = parents(g, 0);
int[] par = pars[0], dep = pars[2];
int[] ord = pars[1], pw = pars[4];
long[] dw = new long[n];
for(int i = 1;i < n;i++){
int cur = ord[i];
dw[cur] = dw[par[cur]] + pw[cur];
}
int[][] spar = logstepParents(par);
int[] cpar = buildCentroidTree(g);
CentroidTreeDistanceArrays ctda = dfsTop(cpar, g);
long[][] gdscum = new long[n][];
for(int i = 0;i < n;i++){
gdscum[i] = new long[ctda.gds[i].length+1];
for(int j = 0;j < ctda.gds[i].length;j++){
gdscum[i][j+1] = gdscum[i][j] + ctda.gds[i][j];
}
}
long[][][] dscum = new long[n][][];
for(int i = 0;i < n;i++){
dscum[i] = new long[ctda.ds[i].length][];
for(int j = 0;j < ctda.ds[i].length;j++){
dscum[i][j] = new long[ctda.ds[i][j].length+1];
for(int k = 0;k < dscum[i][j].length-1;k++){
dscum[i][j][k+1] = dscum[i][j][k] + ctda.ds[i][j][k];
}
}
}
long lownum = 0;
long lowsum = 0;
for(int i = 0;i < n;i++){
int pre = -1;
for(int x = i;x != -1;x = cpar[x]){
int lca = lca2(x, i, spar, dep);
long base = dw[x] + dw[i] - 2*dw[lca];
{
int lb = lowerBound(ctda.gds[x], X-base);
lownum += lb;
lowsum += gdscum[x][lb] + base * lb;
}
if(pre != -1){
int preind = Arrays.binarySearch(ctda.ctch[x], pre);
int lb = lowerBound(ctda.ds[x][preind], X-base);
lownum -= lb;
lowsum -= dscum[x][preind][lb] + base * lb;
}
pre = x;
}
}
for(int i = 1;i < n;i++){
if(pw[i] > X){
lownum += 2;
lowsum += pw[i]*2L;
}
}
lownum = (lownum - n) / 2;
lowsum /= 2;
lowsum += ((long)n*(n-1)/2-lownum) * X;
out.println(lowsum);
}
public static int lowerBound(long[] a, long v)
{
int low = -1, high = a.length;
while(high-low > 1){
int h = high+low>>>1;
if(a[h] >= v){
high = h;
}else{
low = h;
}
}
return high;
}
public static class CentroidTreeDistanceArrays
{
public long[][] gds; // distances subject to v in centroid tree
public long[][][] ds; // distances subject to par[v] in centroid tree and neck is v
public int[][] ctch;
}
/**
* Centroid Treeからの距離配列列挙
* 別に下のseparate関数に処理を追加してもよい
*
* sep : 現在処理しようとするseparator
* seps : マークしたseparatorリスト (volatile)
* q : BFS用キュー (volatile)
* lds : 特定幹部を通る距離配列の一時リスト (volatile)
* glds : sepからの距離配列の一時リスト (volatile)
* dd : sepからの距離配列(頂点からの表引き用) (volatile)
* ds : 特定幹部を通る距離配列
* gds : sepからの距離配列
* g : 辺重み付き木 (const)
* ctch : Centroid Treeの子へのリンク (const)
*
* @param cpar Centroid Treeの親へのリンク
* @param g 辺重み付き木
* @return
*/
public static CentroidTreeDistanceArrays dfsTop(int[] cpar, int[][][] g) {
int n = g.length;
int ctroot = -1;
for(int i = 0;i < n;i++)if(cpar[i] == -1)ctroot = i;
int[][] ctch = parentToChildren(cpar);
for(int[] row : ctch){
Arrays.sort(row);
}
long I = Long.MAX_VALUE / 2;
long[] dd = new long[n];
Arrays.fill(dd, I);
long[][][] ds = new long[n][][];
long[][] gds = new long[n][];
int[] iind = new int[n];
Arrays.fill(iind, -1);
dfs(ctroot, new boolean[n], new int[n], new long[n], new long[n], dd, ds, gds, g, ctch, iind);
CentroidTreeDistanceArrays ret = new CentroidTreeDistanceArrays();
ret.ds = ds;
ret.gds = gds;
ret.ctch = ctch;
return ret;
}
public static int[][] parentToChildren(int[] par)
{
int n = par.length;
int[] ct = new int[n];
for(int i = 0;i < n;i++){
if(par[i] >= 0){
ct[par[i]]++;
}
}
int[][] g = new int[n][];
for(int i = 0;i < n;i++){
g[i] = new int[ct[i]];
}
for(int i = 0;i < n;i++){
if(par[i] >= 0){
g[par[i]][--ct[par[i]]] = i;
}
}
return g;
}
private static void dfs(int sep, boolean[] seps, int[] q, long[] lds, long[] glds, long[] dd, long[][][] ds, long[][] gds, int[][][] g, int[][] ctch, int[] iind)
{
long I = Long.MAX_VALUE / 2;
seps[sep] = true;
int gdp = 0;
dd[sep] = 0;
glds[gdp++] = 0;
for(int i = 0;i < ctch[sep].length;i++){
iind[ctch[sep][i]] = i;
}
ds[sep] = new long[ctch[sep].length][];
for(int[] neck : g[sep]){
int dp = 0;
int p = 0;
int wind = -1;
if(!seps[neck[0]]){
q[p++] = neck[0];
dd[neck[0]] = neck[1];
lds[dp++] = dd[neck[0]];
glds[gdp++] = dd[neck[0]];
for(int j = 0;j < p;j++){
int cur = q[j];
if(iind[cur] != -1)wind = iind[cur];
for(int[] e : g[cur]){
if(!seps[e[0]] && dd[e[0]] == I){
dd[e[0]] = dd[cur] + e[1];
lds[dp++] = dd[e[0]];
glds[gdp++] = dd[e[0]];
q[p++] = e[0];
}
}
}
for(int j = 0;j < p;j++){
dd[q[j]] = I;
}
ds[sep][wind] = Arrays.copyOf(lds, dp);
Arrays.sort(ds[sep][wind]);
}
}
gds[sep] = Arrays.copyOf(glds, gdp);
Arrays.sort(gds[sep]);
for(int i = 0;i < ctch[sep].length;i++){
iind[ctch[sep][i]] = -1;
}
for(int e : ctch[sep]){
dfs(e, seps, q, lds, glds, dd, ds, gds, g, ctch, iind);
}
seps[sep] = false;
}
public static int[] buildCentroidTree(int[][][] g) {
int n = g.length;
int[] ctpar = new int[n];
Arrays.fill(ctpar, -1);
buildCentroidTree(g, 0, new boolean[n], new int[n], new int[n], new int[n], ctpar);
return ctpar;
}
private static int buildCentroidTree(int[][][] g, int root, boolean[] sed, int[] par, int[] ord, int[] des, int[] ctpar)
{
// parent and level-order
ord[0] = root;
par[root] = -1;
int r = 1;
for(int p = 0;p < r;p++) {
int cur = ord[p];
for(int[] nex : g[cur]){
if(par[cur] != nex[0] && !sed[nex[0]]){
ord[r++] = nex[0];
par[nex[0]] = cur;
}
}
}
// if(r == 1)return;
// DP and find a separator
int sep = -1; // always exists
outer:
for(int i = r-1;i >= 0;i--){
int cur = ord[i];
des[cur] = 1;
for(int[] e : g[cur]){
if(par[cur] != e[0] && !sed[e[0]])des[cur] += des[e[0]];
}
if(r-des[cur] <= r/2){
for(int[] e : g[cur]){
if(par[cur] != e[0] && !sed[e[0]] && des[e[0]] >= r/2+1)continue outer;
}
sep = cur;
break;
}
}
sed[sep] = true;
for(int[] e : g[sep]){
if(!sed[e[0]])ctpar[buildCentroidTree(g, e[0], sed, par, ord, des, ctpar)] = sep;
}
return sep;
}
public static int lca2(int a, int b, int[][] spar, int[] depth) {
if (depth[a] < depth[b]) {
b = ancestor(b, depth[b] - depth[a], spar);
} else if (depth[a] > depth[b]) {
a = ancestor(a, depth[a] - depth[b], spar);
}
if (a == b)
return a;
int sa = a, sb = b;
for (int low = 0, high = depth[a], t = Integer.highestOneBit(high), k = Integer
.numberOfTrailingZeros(t); t > 0; t >>>= 1, k--) {
if ((low ^ high) >= t) {
if (spar[k][sa] != spar[k][sb]) {
low |= t;
sa = spar[k][sa];
sb = spar[k][sb];
} else {
high = low | t - 1;
}
}
}
return spar[0][sa];
}
protected static int ancestor(int a, int m, int[][] spar) {
for (int i = 0; m > 0 && a != -1; m >>>= 1, i++) {
if ((m & 1) == 1)
a = spar[i][a];
}
return a;
}
public static int[][] logstepParents(int[] par) {
int n = par.length;
int m = Integer.numberOfTrailingZeros(Integer.highestOneBit(n - 1)) + 1;
int[][] pars = new int[m][n];
pars[0] = par;
for (int j = 1; j < m; j++) {
for (int i = 0; i < n; i++) {
pars[j][i] = pars[j - 1][i] == -1 ? -1 : pars[j - 1][pars[j - 1][i]];
}
}
return pars;
}
public static int[][] parents(int[][][] g, int root) {
int n = g.length;
int[] par = new int[n];
Arrays.fill(par, -1);
int[] dw = new int[n];
int[] pw = new int[n];
int[] dep = new int[n];
int[] q = new int[n];
q[0] = root;
for (int p = 0, r = 1; p < r; p++) {
int cur = q[p];
for (int[] nex : g[cur]) {
if (par[cur] != nex[0]) {
q[r++] = nex[0];
par[nex[0]] = cur;
dep[nex[0]] = dep[cur] + 1;
dw[nex[0]] = dw[cur] + nex[1];
pw[nex[0]] = nex[1];
}
}
}
return new int[][] { par, q, dep, dw, pw };
}
public static int[][][] packWU(int n, int[] from, int[] to, int[] w) {
int[][][] g = new int[n][][];
int[] p = new int[n];
for (int f : from)
p[f]++;
for (int t : to)
p[t]++;
for (int i = 0; i < n; i++)
g[i] = new int[p[i]][2];
for (int i = 0; i < from.length; i++) {
--p[from[i]];
g[from[i]][p[from[i]]][0] = to[i];
g[from[i]][p[from[i]]][1] = w[i];
--p[to[i]];
g[to[i]][p[to[i]]][0] = from[i];
g[to[i]][p[to[i]]][1] = w[i];
}
return g;
}
public static void main(String[] args) throws Exception
{
long S = System.currentTimeMillis();
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
}
private static boolean eof()
{
if(lenbuf == -1)return true;
int lptr = ptrbuf;
while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;
try {
is.mark(1000);
while(true){
int b = is.read();
if(b == -1){
is.reset();
return true;
}else if(!isSpaceChar(b)){
is.reset();
return false;
}
}
} catch (IOException e) {
return true;
}
}
private static byte[] inbuf = new byte[1024];
static int lenbuf = 0, ptrbuf = 0;
private static int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
// private static boolean isSpaceChar(int c) { return !(c >= 32 && c <= 126); }
private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private static double nd() { return Double.parseDouble(ns()); }
private static char nc() { return (char)skip(); }
private static String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private static char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private static char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private static int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private static int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}
Submission Info
Submission Time |
|
Task |
D - 道路網 |
User |
uwi |
Language |
Java8 (OpenJDK 1.8.0) |
Score |
1200 |
Code Size |
13780 Byte |
Status |
AC |
Exec Time |
2541 ms |
Memory |
132492 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1200 / 1200 |
Status |
|
|
Set Name |
Test Cases |
Sample |
00_example_01.txt, 00_example_02.txt |
All |
00_example_01.txt, 00_example_02.txt, 10_rand_01.txt, 10_rand_02.txt, 10_rand_03.txt, 10_rand_04.txt, 10_rand_05.txt, 20_k-ary_01.txt, 20_k-ary_02.txt, 20_k-ary_03.txt, 20_k-ary_04.txt, 20_k-ary_05.txt, 20_k-ary_06.txt, 20_k-ary_07.txt, 20_k-ary_08.txt, 20_k-ary_09.txt, 20_k-ary_10.txt, 30_star_01.txt, 30_star_02.txt, 30_star_03.txt, 30_star_04.txt, 30_star_05.txt, 40_pseudostar_01.txt, 40_pseudostar_02.txt, 40_pseudostar_04.txt, 40_pseudostar_05.txt, 40_pseudostar_06.txt, 50_line_01.txt, 50_line_02.txt, 50_line_03.txt, 60_max_01.txt, 60_max_02.txt, 60_max_03.txt, 60_max_04.txt, 70_hand_01.txt, 70_hand_02.txt, 71_hand_01.txt, 72_hand_01.txt, 80_kill2X_01.txt, 80_kill2X_02.txt, 80_kill2X_03.txt, 80_kill2X_04.txt, 80_kill2X_05.txt, 80_kill2X_06.txt, 80_kill2X_07.txt, 80_kill2X_08.txt |
Case Name |
Status |
Exec Time |
Memory |
00_example_01.txt |
AC |
96 ms |
8276 KB |
00_example_02.txt |
AC |
96 ms |
8144 KB |
10_rand_01.txt |
AC |
108 ms |
9228 KB |
10_rand_02.txt |
AC |
119 ms |
9684 KB |
10_rand_03.txt |
AC |
113 ms |
9424 KB |
10_rand_04.txt |
AC |
120 ms |
9556 KB |
10_rand_05.txt |
AC |
113 ms |
9812 KB |
20_k-ary_01.txt |
AC |
1577 ms |
102852 KB |
20_k-ary_02.txt |
AC |
1452 ms |
103760 KB |
20_k-ary_03.txt |
AC |
1481 ms |
104660 KB |
20_k-ary_04.txt |
AC |
1125 ms |
104996 KB |
20_k-ary_05.txt |
AC |
934 ms |
68092 KB |
20_k-ary_06.txt |
AC |
669 ms |
59384 KB |
20_k-ary_07.txt |
AC |
733 ms |
57744 KB |
20_k-ary_08.txt |
AC |
623 ms |
57592 KB |
20_k-ary_09.txt |
AC |
597 ms |
57136 KB |
20_k-ary_10.txt |
AC |
601 ms |
57416 KB |
30_star_01.txt |
AC |
578 ms |
55788 KB |
30_star_02.txt |
AC |
2541 ms |
55760 KB |
30_star_03.txt |
AC |
485 ms |
55772 KB |
30_star_04.txt |
AC |
614 ms |
56408 KB |
30_star_05.txt |
AC |
1575 ms |
56264 KB |
40_pseudostar_01.txt |
AC |
589 ms |
55768 KB |
40_pseudostar_02.txt |
AC |
524 ms |
56184 KB |
40_pseudostar_04.txt |
AC |
545 ms |
56164 KB |
40_pseudostar_05.txt |
AC |
548 ms |
56700 KB |
40_pseudostar_06.txt |
AC |
562 ms |
56404 KB |
50_line_01.txt |
AC |
2178 ms |
132272 KB |
50_line_02.txt |
AC |
2096 ms |
132492 KB |
50_line_03.txt |
AC |
2141 ms |
132428 KB |
60_max_01.txt |
AC |
1558 ms |
103128 KB |
60_max_02.txt |
AC |
1478 ms |
104700 KB |
60_max_03.txt |
AC |
1329 ms |
104552 KB |
60_max_04.txt |
AC |
1463 ms |
105100 KB |
70_hand_01.txt |
AC |
94 ms |
8148 KB |
70_hand_02.txt |
AC |
96 ms |
8020 KB |
71_hand_01.txt |
AC |
1276 ms |
101132 KB |
72_hand_01.txt |
AC |
1832 ms |
132452 KB |
80_kill2X_01.txt |
AC |
615 ms |
56024 KB |
80_kill2X_02.txt |
AC |
577 ms |
55920 KB |
80_kill2X_03.txt |
AC |
606 ms |
55964 KB |
80_kill2X_04.txt |
AC |
595 ms |
55800 KB |
80_kill2X_05.txt |
AC |
486 ms |
55976 KB |
80_kill2X_06.txt |
AC |
514 ms |
56092 KB |
80_kill2X_07.txt |
AC |
514 ms |
56204 KB |
80_kill2X_08.txt |
AC |
525 ms |
56912 KB |