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) {
        InputReader in = new InputReader(System.in);
        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;
    }

    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 {
                    numChars = stream.read(buf);
                } 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
Task D - 高橋君と木のおもちゃ
User hamadu
Language Java (OpenJDK 1.7.0)
Score 100
Code Size 5946 Byte
Status
Exec Time 690 ms
Memory 28220 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 subtask0-sample-01.txt, subtask0-sample-02.txt
Subtask1 10 / 10 subtask0-sample-01.txt, subtask0-sample-02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask1-21.txt, subtask1-22.txt, subtask1-23.txt, subtask1-24.txt, subtask1-25.txt, subtask1-26.txt, subtask1-27.txt, subtask1-28.txt, subtask1-29.txt, subtask1-30.txt
Subtask2 20 / 20 subtask0-sample-01.txt, subtask0-sample-02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask1-21.txt, subtask1-22.txt, subtask1-23.txt, subtask1-24.txt, subtask1-25.txt, subtask1-26.txt, subtask1-27.txt, subtask1-28.txt, subtask1-29.txt, subtask1-30.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt, subtask2-21.txt, subtask2-22.txt, subtask2-23.txt, subtask2-24.txt, subtask2-25.txt, subtask2-26.txt, subtask2-27.txt, subtask2-28.txt, subtask2-29.txt, subtask2-30.txt
Subtask3 70 / 70 subtask0-sample-01.txt, subtask0-sample-02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask1-21.txt, subtask1-22.txt, subtask1-23.txt, subtask1-24.txt, subtask1-25.txt, subtask1-26.txt, subtask1-27.txt, subtask1-28.txt, subtask1-29.txt, subtask1-30.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt, subtask2-21.txt, subtask2-22.txt, subtask2-23.txt, subtask2-24.txt, subtask2-25.txt, subtask2-26.txt, subtask2-27.txt, subtask2-28.txt, subtask2-29.txt, subtask2-30.txt, subtask3-01.txt, subtask3-02.txt, subtask3-03.txt, subtask3-04.txt, subtask3-05.txt, subtask3-06.txt, subtask3-07.txt, subtask3-08.txt, subtask3-09.txt, subtask3-10.txt, subtask3-11.txt, subtask3-12.txt, subtask3-13.txt, subtask3-14.txt, subtask3-15.txt, subtask3-16.txt, subtask3-17.txt, subtask3-18.txt, subtask3-19.txt, subtask3-20.txt, subtask3-21.txt, subtask3-22.txt, subtask3-23.txt, subtask3-24.txt, subtask3-25.txt, subtask3-26.txt, subtask3-27.txt, subtask3-28.txt, subtask3-29.txt, subtask3-30.txt
Case Name Status Exec Time Memory
subtask0-sample-01.txt 317 ms 20760 KB
subtask0-sample-02.txt 363 ms 20652 KB
subtask1-01.txt 305 ms 20700 KB
subtask1-02.txt 305 ms 20736 KB
subtask1-03.txt 306 ms 20652 KB
subtask1-04.txt 311 ms 20656 KB
subtask1-05.txt 304 ms 20776 KB
subtask1-06.txt 304 ms 20712 KB
subtask1-07.txt 306 ms 20764 KB
subtask1-08.txt 305 ms 20528 KB
subtask1-09.txt 304 ms 20652 KB
subtask1-10.txt 305 ms 20736 KB
subtask1-11.txt 307 ms 20692 KB
subtask1-12.txt 307 ms 20652 KB
subtask1-13.txt 309 ms 20752 KB
subtask1-14.txt 307 ms 20756 KB
subtask1-15.txt 305 ms 20736 KB
subtask1-16.txt 304 ms 20736 KB
subtask1-17.txt 315 ms 20764 KB
subtask1-18.txt 305 ms 20752 KB
subtask1-19.txt 311 ms 20700 KB
subtask1-20.txt 306 ms 20704 KB
subtask1-21.txt 308 ms 20656 KB
subtask1-22.txt 317 ms 20708 KB
subtask1-23.txt 306 ms 20752 KB
subtask1-24.txt 305 ms 20736 KB
subtask1-25.txt 309 ms 20704 KB
subtask1-26.txt 311 ms 20684 KB
subtask1-27.txt 304 ms 20764 KB
subtask1-28.txt 303 ms 20708 KB
subtask1-29.txt 310 ms 20712 KB
subtask1-30.txt 305 ms 20652 KB
subtask2-01.txt 307 ms 20732 KB
subtask2-02.txt 304 ms 20756 KB
subtask2-03.txt 304 ms 20656 KB
subtask2-04.txt 307 ms 20776 KB
subtask2-05.txt 309 ms 20776 KB
subtask2-06.txt 316 ms 20648 KB
subtask2-07.txt 304 ms 20732 KB
subtask2-08.txt 311 ms 20772 KB
subtask2-09.txt 307 ms 20736 KB
subtask2-10.txt 304 ms 20656 KB
subtask2-11.txt 305 ms 20780 KB
subtask2-12.txt 303 ms 20732 KB
subtask2-13.txt 306 ms 20724 KB
subtask2-14.txt 308 ms 20704 KB
subtask2-15.txt 307 ms 20704 KB
subtask2-16.txt 305 ms 20652 KB
subtask2-17.txt 313 ms 20780 KB
subtask2-18.txt 303 ms 20704 KB
subtask2-19.txt 311 ms 20748 KB
subtask2-20.txt 308 ms 20732 KB
subtask2-21.txt 304 ms 20736 KB
subtask2-22.txt 306 ms 20652 KB
subtask2-23.txt 306 ms 20780 KB
subtask2-24.txt 313 ms 20712 KB
subtask2-25.txt 314 ms 20732 KB
subtask2-26.txt 378 ms 20736 KB
subtask2-27.txt 304 ms 20776 KB
subtask2-28.txt 334 ms 21744 KB
subtask2-29.txt 370 ms 22664 KB
subtask2-30.txt 342 ms 22868 KB
subtask3-01.txt 332 ms 22432 KB
subtask3-02.txt 358 ms 23384 KB
subtask3-03.txt 364 ms 23600 KB
subtask3-04.txt 352 ms 23092 KB
subtask3-05.txt 439 ms 27060 KB
subtask3-06.txt 422 ms 25892 KB
subtask3-07.txt 563 ms 27668 KB
subtask3-08.txt 690 ms 23316 KB
subtask3-09.txt 576 ms 24464 KB
subtask3-10.txt 513 ms 27608 KB
subtask3-11.txt 577 ms 27532 KB
subtask3-12.txt 609 ms 26708 KB
subtask3-13.txt 636 ms 26564 KB
subtask3-14.txt 574 ms 27644 KB
subtask3-15.txt 660 ms 27776 KB
subtask3-16.txt 607 ms 27824 KB
subtask3-17.txt 488 ms 26708 KB
subtask3-18.txt 534 ms 27976 KB
subtask3-19.txt 492 ms 26344 KB
subtask3-20.txt 517 ms 26476 KB
subtask3-21.txt 527 ms 28112 KB
subtask3-22.txt 526 ms 28036 KB
subtask3-23.txt 490 ms 26712 KB
subtask3-24.txt 554 ms 27684 KB
subtask3-25.txt 498 ms 26736 KB
subtask3-26.txt 550 ms 28220 KB
subtask3-27.txt 506 ms 26680 KB
subtask3-28.txt 557 ms 27612 KB
subtask3-29.txt 528 ms 26612 KB
subtask3-30.txt 511 ms 27920 KB