Contest Duration: - (local time) (90 minutes) Back to Home

Submission #242885

Source Code Expand

Copy
```import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.InputMismatchException;

/**
* Created by hama_du on 2014/09/27.
*/
public class Main {
static int[][] graph;
static long[][] sum;
static long[] a;

static void dfs(int now, int parent) {
sum[now][0] = 0;
sum[now][1] = Math.min(sum[now][1], a[now]);

int sl = sum[now].length;

for (int to : graph[now]) {
if (to == parent) {
continue;
}

dfs(to, now);

long[] part = sum[to];
for (int t = sl-1 ; t >= 2 ; t--) {
for (int p = 1 ; p < sl ; p++) {
if (sum[now][p] == Long.MAX_VALUE) {
break;
}
int pp = t - p;
if (pp <= 0) {
break;
}
if (part[pp] < Long.MAX_VALUE) {
sum[now][t] = Math.min(sum[now][t], sum[now][p] + part[pp]);
}
}
}
}
}

public static void main(String[] args) {
PrintWriter out = new PrintWriter(System.out);

int n = in.nextInt();
a = new long[n];
for (int i = 0; i < n; i++) {
a[i] = in.nextLong();
}

graph = buildGraph(in, n, n-1);
sum = new long[n][n+1];
for (int i = 0 ; i < n ; i++) {
Arrays.fill(sum[i], Long.MAX_VALUE);
}

int m = in.nextInt();
long[] r = new long[m];
for (int i = 0 ; i < m ; i++) {
r[i] = in.nextLong();
}
Arrays.sort(r);

dfs(0, -1);

long all = 0;
for (int i = 0 ; i < a.length ; i++) {
all += a[i];
}

long max = all;
long get = 0;
long lose = 0;
for (int u = 1 ; u <= Math.min(a.length, r.length) ; u++) {
get += r[r.length-u];
lose = sum[0][u];
long p = all + get - lose;
max = Math.max(max, p);
}

out.println(max);
out.flush();
}
public static void debug(Object... o) {
System.err.println(Arrays.deepToString(o));
}

static int[][] buildGraph(InputReader in, int n, int m) {
int[][] edges = new int[m][];
int[][] graph = new int[n][];
int[] deg = new int[n];
for (int i = 0 ; i < m ; i++) {
int a = in.nextInt()-1;
int b = in.nextInt()-1;
deg[a]++;
deg[b]++;
edges[i] = new int[]{a, b};
}
for (int i = 0 ; i < n ; i++) {
graph[i] = new int[deg[i]];
}
for (int i = 0 ; i < m ; i++) {
int a = edges[i][0];
int b = edges[i][1];
graph[a][--deg[a]] = b;
graph[b][--deg[b]] = a;
}
return graph;
}

private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
private SpaceCharFilter filter;

this.stream = stream;
}

public int next() {
if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}

public int nextInt() {
int c = next();
while (isSpaceChar(c))
c = next();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = next();
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = next();
} while (!isSpaceChar(c));
return res * sgn;
}

public long nextLong() {
int c = next();
while (isSpaceChar(c))
c = next();
long sgn = 1;
if (c == '-') {
sgn = -1;
c = next();
}
long res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = next();
} while (!isSpaceChar(c));
return res * sgn;
}

public boolean isSpaceChar(int c) {
if (filter != null)
return filter.isSpaceChar(c);
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}

public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}
}
```

#### Submission Info

Submission Time 2014-09-28 13:36:49+0900 D - 高橋君と木のおもちゃ hamadu Java (OpenJDK 1.7.0) 30 5491 Byte TLE 2085 ms 267332 KB

#### Judge Result

Score / Max Score 0 / 0 10 / 10 20 / 20 0 / 70
Status
 AC × 2
 AC × 32
 AC × 62
 AC × 68 TLE × 24
Set Name Test Cases
Case Name Status Exec Time Memory
subtask0-sample-01.txt AC 380 ms 20744 KB
subtask0-sample-02.txt AC 370 ms 20724 KB
subtask1-01.txt AC 377 ms 20804 KB
subtask1-02.txt AC 375 ms 20728 KB
subtask1-03.txt AC 373 ms 20768 KB
subtask1-04.txt AC 377 ms 20728 KB
subtask1-05.txt AC 380 ms 20832 KB
subtask1-06.txt AC 378 ms 20752 KB
subtask1-07.txt AC 382 ms 20844 KB
subtask1-08.txt AC 371 ms 20856 KB
subtask1-09.txt AC 368 ms 20792 KB
subtask1-10.txt AC 377 ms 20804 KB
subtask1-11.txt AC 374 ms 20816 KB
subtask1-12.txt AC 422 ms 20752 KB
subtask1-13.txt AC 406 ms 20768 KB
subtask1-14.txt AC 407 ms 20696 KB
subtask1-15.txt AC 387 ms 20696 KB
subtask1-16.txt AC 390 ms 20772 KB
subtask1-17.txt AC 396 ms 20724 KB
subtask1-18.txt AC 372 ms 20764 KB
subtask1-19.txt AC 378 ms 20724 KB
subtask1-20.txt AC 400 ms 20804 KB
subtask1-21.txt AC 410 ms 20784 KB
subtask1-22.txt AC 408 ms 20760 KB
subtask1-23.txt AC 397 ms 20792 KB
subtask1-24.txt AC 394 ms 20736 KB
subtask1-25.txt AC 394 ms 20724 KB
subtask1-26.txt AC 378 ms 20760 KB
subtask1-27.txt AC 379 ms 20692 KB
subtask1-28.txt AC 390 ms 20796 KB
subtask1-29.txt AC 384 ms 20764 KB
subtask1-30.txt AC 384 ms 20768 KB
subtask2-01.txt AC 402 ms 20764 KB
subtask2-02.txt AC 374 ms 20804 KB
subtask2-03.txt AC 390 ms 20764 KB
subtask2-04.txt AC 370 ms 20656 KB
subtask2-05.txt AC 370 ms 20804 KB
subtask2-06.txt AC 366 ms 20752 KB
subtask2-07.txt AC 373 ms 20768 KB
subtask2-08.txt AC 376 ms 20804 KB
subtask2-09.txt AC 384 ms 20788 KB
subtask2-10.txt AC 377 ms 20856 KB
subtask2-11.txt AC 364 ms 20728 KB
subtask2-12.txt AC 378 ms 20772 KB
subtask2-13.txt AC 369 ms 20764 KB
subtask2-14.txt AC 372 ms 20864 KB
subtask2-15.txt AC 387 ms 20788 KB
subtask2-16.txt AC 373 ms 20760 KB
subtask2-17.txt AC 377 ms 20660 KB
subtask2-18.txt AC 379 ms 20764 KB
subtask2-19.txt AC 382 ms 20828 KB
subtask2-20.txt AC 389 ms 20652 KB
subtask2-21.txt AC 373 ms 20708 KB
subtask2-22.txt AC 373 ms 20764 KB
subtask2-23.txt AC 379 ms 20796 KB
subtask2-24.txt AC 376 ms 20704 KB
subtask2-25.txt AC 379 ms 20772 KB
subtask2-26.txt AC 373 ms 20736 KB
subtask2-27.txt AC 383 ms 20728 KB
subtask2-28.txt AC 410 ms 21944 KB
subtask2-29.txt AC 410 ms 22236 KB
subtask2-30.txt AC 423 ms 22700 KB
subtask3-01.txt AC 420 ms 23376 KB
subtask3-02.txt AC 479 ms 27224 KB
subtask3-03.txt AC 561 ms 36576 KB
subtask3-04.txt AC 548 ms 36240 KB
subtask3-05.txt AC 917 ms 57804 KB
subtask3-06.txt AC 1600 ms 96424 KB
subtask3-07.txt TLE 2053 ms 168636 KB
subtask3-08.txt TLE 2065 ms 264284 KB
subtask3-09.txt TLE 2064 ms 263836 KB
subtask3-10.txt TLE 2069 ms 266472 KB
subtask3-11.txt TLE 2063 ms 266204 KB
subtask3-12.txt TLE 2062 ms 266900 KB
subtask3-13.txt TLE 2069 ms 266532 KB
subtask3-14.txt TLE 2085 ms 266904 KB
subtask3-15.txt TLE 2066 ms 266372 KB
subtask3-16.txt TLE 2071 ms 267044 KB
subtask3-17.txt TLE 2067 ms 266836 KB
subtask3-18.txt TLE 2068 ms 266800 KB
subtask3-19.txt TLE 2067 ms 266528 KB
subtask3-20.txt TLE 2065 ms 266476 KB
subtask3-21.txt TLE 2063 ms 267332 KB
subtask3-22.txt TLE 2065 ms 266784 KB
subtask3-23.txt TLE 2065 ms 266820 KB
subtask3-24.txt TLE 2067 ms 266764 KB
subtask3-25.txt TLE 2066 ms 266828 KB
subtask3-26.txt TLE 2063 ms 266492 KB
subtask3-27.txt TLE 2063 ms 266724 KB
subtask3-28.txt TLE 2069 ms 266380 KB
subtask3-29.txt TLE 2066 ms 266620 KB
subtask3-30.txt TLE 2067 ms 266768 KB