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

Submission #242889

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 int dfs(int now, int parent) {
int ret = 1;

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;
}

int ch = dfs(to, now);
ret += ch;

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

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;
}

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

public InputReader(InputStream stream) {
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:53:15+0900 D - 高橋君と木のおもちゃ hamadu Java (OpenJDK 1.7.0) 30 5569 Byte MLE 1171 ms 268272 KB

#### Test Cases

Set Name Score / Max Score Test Cases
Case Name Status Exec Time Memory
subtask0-sample-01.txt 323 ms 20752 KB
subtask0-sample-02.txt 330 ms 20804 KB
subtask1-01.txt 320 ms 20784 KB
subtask1-02.txt 317 ms 20768 KB
subtask1-03.txt 324 ms 20772 KB
subtask1-04.txt 322 ms 20772 KB
subtask1-05.txt 325 ms 20772 KB
subtask1-06.txt 324 ms 20768 KB
subtask1-07.txt 324 ms 20772 KB
subtask1-08.txt 353 ms 20744 KB
subtask1-09.txt 319 ms 20772 KB
subtask1-10.txt 320 ms 20816 KB
subtask1-11.txt 324 ms 20760 KB
subtask1-12.txt 319 ms 20768 KB
subtask1-13.txt 330 ms 20772 KB
subtask1-14.txt 325 ms 20732 KB
subtask1-15.txt 326 ms 20772 KB
subtask1-16.txt 326 ms 20772 KB
subtask1-17.txt 332 ms 20788 KB
subtask1-18.txt 327 ms 20788 KB
subtask1-19.txt 327 ms 20804 KB
subtask1-20.txt 334 ms 20820 KB
subtask1-21.txt 323 ms 20772 KB
subtask1-22.txt 326 ms 20664 KB
subtask1-23.txt 331 ms 20752 KB
subtask1-24.txt 324 ms 20768 KB
subtask1-25.txt 327 ms 20692 KB
subtask1-26.txt 324 ms 20660 KB
subtask1-27.txt 323 ms 20768 KB
subtask1-28.txt 323 ms 20772 KB
subtask1-29.txt 323 ms 20760 KB
subtask1-30.txt 322 ms 20784 KB
subtask2-01.txt 320 ms 20760 KB
subtask2-02.txt 323 ms 20788 KB
subtask2-03.txt 329 ms 20796 KB
subtask2-04.txt 331 ms 20736 KB
subtask2-05.txt 345 ms 20760 KB
subtask2-06.txt 349 ms 20768 KB
subtask2-07.txt 358 ms 20788 KB
subtask2-08.txt 332 ms 20684 KB
subtask2-09.txt 333 ms 20768 KB
subtask2-10.txt 333 ms 20768 KB
subtask2-11.txt 333 ms 20768 KB
subtask2-12.txt 333 ms 20768 KB
subtask2-13.txt 330 ms 20768 KB
subtask2-14.txt 329 ms 20768 KB
subtask2-15.txt 331 ms 20736 KB
subtask2-16.txt 328 ms 20752 KB
subtask2-17.txt 320 ms 20684 KB
subtask2-18.txt 331 ms 20784 KB
subtask2-19.txt 320 ms 20800 KB
subtask2-20.txt 324 ms 20784 KB
subtask2-21.txt 319 ms 20756 KB
subtask2-22.txt 325 ms 20772 KB
subtask2-23.txt 322 ms 20720 KB
subtask2-24.txt 322 ms 20784 KB
subtask2-25.txt 323 ms 20772 KB
subtask2-26.txt 326 ms 20800 KB
subtask2-27.txt 321 ms 20772 KB
subtask2-28.txt 357 ms 22580 KB
subtask2-29.txt 366 ms 23224 KB
subtask2-30.txt 358 ms 22476 KB
subtask3-01.txt 358 ms 23228 KB
subtask3-02.txt 391 ms 28240 KB
subtask3-03.txt 417 ms 37288 KB
subtask3-04.txt 422 ms 37272 KB
subtask3-05.txt 492 ms 57100 KB
subtask3-06.txt 636 ms 97272 KB
subtask3-07.txt 842 ms 169844 KB
subtask3-08.txt 1015 ms 263592 KB
subtask3-09.txt 1020 ms 264264 KB
subtask3-10.txt 1059 ms 266456 KB
subtask3-11.txt 1116 ms 267848 KB
subtask3-12.txt 1024 ms 266464 KB
subtask3-13.txt 1036 ms 267360 KB
subtask3-14.txt 1079 ms 267388 KB
subtask3-15.txt 1090 ms 267736 KB
subtask3-16.txt 1171 ms 267780 KB
subtask3-17.txt 1033 ms 266760 KB
subtask3-18.txt 1052 ms 267692 KB
subtask3-19.txt 1050 ms 266704 KB
subtask3-20.txt 1065 ms 266516 KB
subtask3-21.txt 1070 ms 268152 KB
subtask3-22.txt 1030 ms 266716 KB
subtask3-23.txt 1022 ms 266224 KB
subtask3-24.txt 1054 ms 267276 KB
subtask3-25.txt 1057 ms 267728 KB
subtask3-26.txt 1080 ms 268272 KB
subtask3-27.txt 1027 ms 266836 KB
subtask3-28.txt 1078 ms 267800 KB
subtask3-29.txt 1061 ms 266468 KB
subtask3-30.txt 1057 ms 267688 KB