Submission #2513767


Source Code Expand

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;

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

        int n = in.nextInt();
        graph = buildGraph(in, n, n-1);
        char[] s = in.nextToken().toCharArray();
        color = new int[n];
        for (int i = 0; i < n ; i++) {
            color[i] = s[i] == 'W' ? 0 : 1;
        }

        out.println(solve());
        out.flush();
    }

    static void cutBlackLeaf() {
        int n = graph.length;
        available = new boolean[n];
        Arrays.fill(available, true);

        int[] deg = new int[n];
        int[] que = new int[n];
        int qh = 0;
        for (int i = 0; i < n ; i++) {
            deg[i] = graph[i].length;
            if (deg[i] == 1) {
                if (color[i] == 1) {
                    que[qh++] = i;
                }
            }
        }
        int qt = 0;
        while (qt < qh) {
            int now = que[qt++];
            available[now] = false;
            for (int to : graph[now]) {
                deg[to]--;
                if (deg[to] == 1 && color[to] == 1 && available[to]) {
                    que[qh++] = to;
                }
            }
        }

        for (int i = 0; i < n ; i++) {
            if (available[i]) {
                int de = 0;
                int[] cp = graph[i].clone();
                for (int to : cp) {
                    if (available[to]) {
                        de++;
                    }
                }
                graph[i] = new int[de];
                for (int to : cp) {
                    if (available[to]) {
                        graph[i][--de] = to;
                    }
                }
            } else {
                graph[i] = null;
            }
        }

    }

    static int solve() {
        int n = graph.length;


        if (n == 1) {
            return color[0]^1;
        }

        available = new boolean[n];
        cutBlackLeaf();

        int root = -1;
        int vc = 0;
        for (int i = 0; i < n ; i++) {
            if (available[i]) {
                vc++;
                if (graph[i].length >= 2) {
                    root = i;
                }
            }
        }
        if (vc <= 1) {
            // W or nothing
            return vc;
        }
        if (root == -1) {
            // W-W
            return 2;
        }

        int total = 0;
        for (int i = 0; i < n ; i++) {
            if (available[i]) {
                int gd = graph[i].length;
                color[i] ^= gd % 2;
                total += color[i] ^ 1;
            }
        }
        return (vc - 1) * 2 + total - find(root) * 2;
    }

    static int find(int rt) {
        int[] x = dfs0(rt, -1);
        int[] y = dfs0(x[1], -1);
        return y[0];
    }

    static int[] dfs0(int now, int par) {
        int[] best = new int[]{-1, -1};
        for (int to : graph[now]) {
            if (to == par || !available[to]) {
                continue;
            }
            int[] t = dfs0(to, now);
            if (best[0] < t[0]) {
                best = t.clone();
            }
        }
        if (best[0] == -1) {
            return new int[]{0, now};
        }
        best[0] += color[now] ^ 1;
        return best;
    }

    static boolean[] available;

    static int[] color;
    static int[][] graph;

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

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

    public static class InputReader {
        private static final int BUFFER_LENGTH = 1 << 12;
        private InputStream stream;
        private byte[] buf = new byte[BUFFER_LENGTH];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        private 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 char nextChar() {
            return (char) skipWhileSpace();
        }

        public String nextToken() {
            int c = skipWhileSpace();
            StringBuilder res = new StringBuilder();
            do {
                res.append((char) c);
                c = next();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public int nextInt() {
            return (int) nextLong();
        }

        public long nextLong() {
            int c = skipWhileSpace();
            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 double nextDouble() {
            return Double.valueOf(nextToken());
        }

        int skipWhileSpace() {
            int c = next();
            while (isSpaceChar(c)) {
                c = next();
            }
            return c;
        }

        boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
    }
}

Submission Info

Submission Time
Task F - Monochrome Cat
User hamadu
Language Java8 (OpenJDK 1.8.0)
Score 800
Code Size 6774 Byte
Status AC
Exec Time 231 ms
Memory 53544 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 800 / 800
Status
AC × 4
AC × 118
Set Name Test Cases
Sample 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt
All 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 1_033.txt, 1_034.txt, 1_035.txt, 1_036.txt, 1_037.txt, 1_038.txt, 1_039.txt, 1_040.txt, 1_041.txt, 1_042.txt, 1_043.txt, 1_044.txt, 1_045.txt, 1_046.txt, 1_047.txt, 1_048.txt, 1_049.txt, 1_050.txt, 1_051.txt, 1_052.txt, 1_053.txt, 1_054.txt, 1_055.txt, 1_056.txt, 1_057.txt, 1_058.txt, 1_059.txt, 1_060.txt, 1_061.txt, 1_062.txt, 1_063.txt, 1_064.txt, 1_065.txt, 1_066.txt, 1_067.txt, 1_068.txt, 1_069.txt, 1_070.txt, 1_071.txt, 1_072.txt, 1_073.txt, 1_074.txt, 1_075.txt, 1_076.txt, 1_077.txt, 1_078.txt, 1_079.txt, 1_080.txt, 1_081.txt, 1_082.txt, 1_083.txt, 1_084.txt, 1_085.txt, 1_086.txt, 1_087.txt, 1_088.txt, 1_089.txt, 1_090.txt, 1_091.txt, 1_092.txt, 1_093.txt, 1_094.txt, 1_095.txt, 1_096.txt, 1_097.txt, 1_098.txt, 1_099.txt, 1_100.txt, 1_101.txt, 1_102.txt, 1_103.txt, 1_104.txt, 1_105.txt, 1_106.txt, 1_107.txt, 1_108.txt, 1_109.txt, 1_110.txt, 1_111.txt, 1_112.txt, 1_113.txt, 1_114.txt, 1_115.txt, 1_116.txt
Case Name Status Exec Time Memory
0_000.txt AC 69 ms 19156 KB
0_001.txt AC 68 ms 18900 KB
0_002.txt AC 69 ms 19156 KB
0_003.txt AC 70 ms 19028 KB
1_003.txt AC 68 ms 21204 KB
1_004.txt AC 68 ms 19156 KB
1_005.txt AC 69 ms 21204 KB
1_006.txt AC 69 ms 18900 KB
1_007.txt AC 69 ms 19924 KB
1_008.txt AC 69 ms 18260 KB
1_009.txt AC 69 ms 18132 KB
1_010.txt AC 68 ms 19156 KB
1_011.txt AC 68 ms 18260 KB
1_012.txt AC 68 ms 18260 KB
1_013.txt AC 69 ms 18772 KB
1_014.txt AC 67 ms 17492 KB
1_015.txt AC 69 ms 18260 KB
1_016.txt AC 70 ms 19284 KB
1_017.txt AC 71 ms 18772 KB
1_018.txt AC 67 ms 17620 KB
1_019.txt AC 67 ms 19284 KB
1_020.txt AC 69 ms 20564 KB
1_021.txt AC 67 ms 17620 KB
1_022.txt AC 69 ms 18900 KB
1_023.txt AC 69 ms 18388 KB
1_024.txt AC 68 ms 21204 KB
1_025.txt AC 68 ms 17364 KB
1_026.txt AC 69 ms 18260 KB
1_027.txt AC 71 ms 18772 KB
1_028.txt AC 71 ms 18772 KB
1_029.txt AC 67 ms 19540 KB
1_030.txt AC 69 ms 17876 KB
1_031.txt AC 68 ms 19796 KB
1_032.txt AC 69 ms 19412 KB
1_033.txt AC 68 ms 20564 KB
1_034.txt AC 69 ms 21076 KB
1_035.txt AC 68 ms 19284 KB
1_036.txt AC 70 ms 21076 KB
1_037.txt AC 69 ms 19024 KB
1_038.txt AC 71 ms 18260 KB
1_039.txt AC 71 ms 19156 KB
1_040.txt AC 70 ms 19156 KB
1_041.txt AC 69 ms 18900 KB
1_042.txt AC 70 ms 18772 KB
1_043.txt AC 69 ms 21076 KB
1_044.txt AC 68 ms 19156 KB
1_045.txt AC 143 ms 33088 KB
1_046.txt AC 150 ms 36408 KB
1_047.txt AC 146 ms 28372 KB
1_048.txt AC 141 ms 25940 KB
1_049.txt AC 204 ms 45208 KB
1_050.txt AC 185 ms 41376 KB
1_051.txt AC 177 ms 42952 KB
1_052.txt AC 102 ms 20948 KB
1_053.txt AC 137 ms 25812 KB
1_054.txt AC 117 ms 21460 KB
1_055.txt AC 176 ms 40704 KB
1_056.txt AC 125 ms 24404 KB
1_057.txt AC 77 ms 20692 KB
1_058.txt AC 158 ms 34388 KB
1_059.txt AC 119 ms 21844 KB
1_060.txt AC 141 ms 25812 KB
1_061.txt AC 192 ms 45300 KB
1_062.txt AC 152 ms 32056 KB
1_063.txt AC 162 ms 38596 KB
1_064.txt AC 141 ms 29524 KB
1_065.txt AC 84 ms 19156 KB
1_066.txt AC 139 ms 27348 KB
1_067.txt AC 113 ms 25556 KB
1_068.txt AC 141 ms 26580 KB
1_069.txt AC 123 ms 26156 KB
1_070.txt AC 144 ms 30036 KB
1_071.txt AC 141 ms 27988 KB
1_072.txt AC 126 ms 24148 KB
1_073.txt AC 107 ms 21076 KB
1_074.txt AC 83 ms 19540 KB
1_075.txt AC 154 ms 29136 KB
1_076.txt AC 199 ms 39516 KB
1_077.txt AC 140 ms 27348 KB
1_078.txt AC 114 ms 21332 KB
1_079.txt AC 141 ms 32192 KB
1_080.txt AC 150 ms 28364 KB
1_081.txt AC 210 ms 49120 KB
1_082.txt AC 214 ms 47380 KB
1_083.txt AC 149 ms 27476 KB
1_084.txt AC 148 ms 30036 KB
1_085.txt AC 200 ms 49952 KB
1_086.txt AC 231 ms 53544 KB
1_087.txt AC 197 ms 38568 KB
1_088.txt AC 179 ms 39212 KB
1_089.txt AC 136 ms 27860 KB
1_090.txt AC 132 ms 27220 KB
1_091.txt AC 194 ms 40756 KB
1_092.txt AC 133 ms 30548 KB
1_093.txt AC 201 ms 45080 KB
1_094.txt AC 224 ms 46300 KB
1_095.txt AC 149 ms 28500 KB
1_096.txt AC 149 ms 27988 KB
1_097.txt AC 207 ms 43024 KB
1_098.txt AC 197 ms 46636 KB
1_099.txt AC 193 ms 39708 KB
1_100.txt AC 198 ms 40144 KB
1_101.txt AC 134 ms 28884 KB
1_102.txt AC 145 ms 28500 KB
1_103.txt AC 189 ms 39088 KB
1_104.txt AC 174 ms 36940 KB
1_105.txt AC 194 ms 42864 KB
1_106.txt AC 189 ms 39892 KB
1_107.txt AC 149 ms 28244 KB
1_108.txt AC 148 ms 26836 KB
1_109.txt AC 194 ms 40712 KB
1_110.txt AC 185 ms 40464 KB
1_111.txt AC 191 ms 37532 KB
1_112.txt AC 198 ms 40648 KB
1_113.txt AC 147 ms 28596 KB
1_114.txt AC 146 ms 27348 KB
1_115.txt AC 189 ms 40872 KB
1_116.txt AC 182 ms 39240 KB