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

Submission #242894

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[] cnt;

static int dfs0(int now, int parent) {
int ret = 1;
for (int to : graph[now]) {
if (to == parent) {
continue;
}
ret += dfs0(to, now);
}
cnt[now] = ret;
return ret;
}

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

dfs(to, now);
ret += cnt[to];

long[] part = sum[to];
for (int t = ret ; t >= 2 ; t--) {
for (int pp = 1 ; pp < part.length ; pp++) {
if (part[pp] == Long.MAX_VALUE) {
break;
}
int p = t - pp;
if (p <= 0) {
break;
}
if (sum[now][p] < 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);
cnt = new int[n];
dfs0(0, -1);

sum = new long[n][];
for (int i = 0 ; i < n ; i++) {
sum[i] = new long[cnt[i]+1];
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 14:01:25+0900 D - 高橋君と木のおもちゃ hamadu Java (OpenJDK 1.7.0) 100 5946 Byte AC 690 ms 28220 KB

#### Test Cases

Set Name Score / Max Score Test Cases
Case Name Status Exec Time Memory