Submission #2501948


Source Code Expand

using System;
using System.Collections.Generic;
using System.Linq;
using System.Linq.Expressions;
using System.IO;
using System.Text;
using System.Diagnostics;

using static util;
using P = pair<int, int>;

using Binary = System.Func<System.Linq.Expressions.ParameterExpression, System.Linq.Expressions.ParameterExpression,
                           System.Linq.Expressions.BinaryExpression>;
using Unary = System.Func<System.Linq.Expressions.ParameterExpression, System.Linq.Expressions.UnaryExpression>;

class Program
{
    static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
    static Scan sc = new Scan();
    const int M = 1000000007;
    // const int M = 998244353;
    const long LM = (long)1e18;
    const double eps = 1e-11;
    static readonly int[] dd = { 0, 1, 0, -1, 0 };
    const string dstring = "RDLU";
    static void Main()
    {
        int n = sc.Int;
        edge = new List<int>[n];
        for (int i = 0; i < n; i++)
        {
            edge[i] = new List<int>();
        }
        for (int i = 0; i < n - 1; i++)
        {
            int a, b;
            sc.Multi(out a, out b);
            --a;
            --b;
            edge[a].Add(b);
            edge[b].Add(a);
        }
        isw = sc.Str.Select(x => x == 'W').ToArray();
        var wlis = new List<int>();
        for (int i = 0; i < n; i++)
        {
            if (isw[i]) wlis.Add(i);
        }
        if (wlis.Count == 0) {
            DBG(0);
            return;
        }
        if (wlis.Count == 1) {
            DBG(1);
            return;
        }
        use = new bool[n];
        dfs(wlis[0], -1);
        cost = new int[n];
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            if (!use[i]) continue;
            int c = 0;
            foreach (var item in edge[i])
            {
                if (use[item]) ++c;
            }
            if ((c % 2 == 1) == isw[i])
                ans += c;
            else {
                ans += c + 1;
                cost[i] = 2;
            }
        }
        calcchildmax(wlis[0], -1);
        Prt(ans - pathmax);
        sw.Flush();
    }
    static List<int>[] edge;
    static bool[] isw;
    static bool[] use;
    static bool dfs(int p, int par) {
        bool ret = isw[p];
        foreach (var item in edge[p])
        {
            if (item == par) continue;
            ret = dfs(item, p) | ret;
        }
        return use[p] = ret;
    }
    static int pathmax;
    static int[] cost;
    static int calcchildmax(int p, int par) {
        int max = 0, sec = 0;
        foreach (var item in edge[p])
        {
            if (item == par) continue;
            int c = calcchildmax(item, p);
            if (c > max) {
                sec = max;
                max = c;
            }
            else if (c > sec) {
                sec = c;
            }
        }
        pathmax = Math.Max(pathmax, max + sec + cost[p]);
        return max + cost[p];
    }

    static void DBG(string a) => Console.WriteLine(a);
    static void DBG<T>(IEnumerable<T> a) => DBG(string.Join(" ", a));
    static void DBG(params object[] a) => DBG(string.Join(" ", a));
    static void Prt(string a) => sw.WriteLine(a);
    static void Prt<T>(IEnumerable<T> a) => Prt(string.Join(" ", a));
    static void Prt(params object[] a) => Prt(string.Join(" ", a));
}
class pair<T, U> : IComparable<pair<T, U>> where T : IComparable<T> where U : IComparable<U>
{
    public T v1;
    public U v2;
    public pair(T v1, U v2) {
        this.v1 = v1;
        this.v2 = v2;
    }
    public int CompareTo(pair<T, U> a) => v1.CompareTo(a.v1) != 0 ? v1.CompareTo(a.v1) : v2.CompareTo(a.v2);
    public override string ToString() => v1 + " " + v2;
}
static class util
{
    public static pair<T, T> make_pair<T>(this IList<T> l) where T : IComparable<T> => make_pair(l[0], l[1]);
    public static pair<T, U> make_pair<T, U>(T v1, U v2) where T : IComparable<T> where U : IComparable<U> => new pair<T, U>(v1, v2);
    public static T sqr<T>(T a) => Operator<T>.Multiply(a, a);
    public static T Max<T>(params T[] a) => a.Max();
    public static T Min<T>(params T[] a) => a.Min();
    public static bool inside(int i, int j, int h, int w) => i >= 0 && i < h && j >= 0 && j < w;
    public static void swap<T>(ref T a, ref T b) { var t = a; a = b; b = t; }
    public static void swap<T>(this IList<T> a, int i, int j) { var t = a[i]; a[i] = a[j]; a[j] = t; }
    public static T[] copy<T>(this IList<T> a) {
        var ret = new T[a.Count];
        for (int i = 0; i < a.Count; i++) ret[i] = a[i];
        return ret;
    }
}
static class Operator<T>
{
    static readonly ParameterExpression x = Expression.Parameter(typeof(T), "x");
    static readonly ParameterExpression y = Expression.Parameter(typeof(T), "y");
    public static readonly Func<T, T, T> Add = Lambda(Expression.Add);
    public static readonly Func<T, T, T> Subtract = Lambda(Expression.Subtract);
    public static readonly Func<T, T, T> Multiply = Lambda(Expression.Multiply);
    public static readonly Func<T, T, T> Divide = Lambda(Expression.Divide);
    public static readonly Func<T, T> Plus = Lambda(Expression.UnaryPlus);
    public static readonly Func<T, T> Negate = Lambda(Expression.Negate);
    public static Func<T, T, T> Lambda(Binary op) => Expression.Lambda<Func<T, T, T>>(op(x, y), x, y).Compile();
    public static Func<T, T> Lambda(Unary op) => Expression.Lambda<Func<T, T>>(op(x), x).Compile();
}

class Scan
{
    public int Int => int.Parse(Str);
    public long Long => long.Parse(Str);
    public double Double => double.Parse(Str);
    public string Str => Console.ReadLine().Trim();
    public pair<T, U> Pair<T, U>() where T : IComparable<T> where U : IComparable<U>
    { T a; U b; Multi(out a, out b); return new pair<T, U>(a, b); }
    public int[] IntArr => StrArr.Select(int.Parse).ToArray();
    public long[] LongArr => StrArr.Select(long.Parse).ToArray();
    public double[] DoubleArr => StrArr.Select(double.Parse).ToArray();
    public string[] StrArr => Str.Split(new []{' '}, System.StringSplitOptions.RemoveEmptyEntries);
    bool eq<T, U>() => typeof(T).Equals(typeof(U));
    T ct<T, U>(U a) => (T)Convert.ChangeType(a, typeof(T));
    T cv<T>(string s) => eq<T, int>()    ? ct<T, int>(int.Parse(s))
                       : eq<T, long>()   ? ct<T, long>(long.Parse(s))
                       : eq<T, double>() ? ct<T, double>(double.Parse(s))
                       : eq<T, char>()   ? ct<T, char>(s[0])
                                         : ct<T, string>(s);
    public void Multi<T>(out T a) => a = cv<T>(Str);
    public void Multi<T, U>(out T a, out U b)
    { var ar = StrArr; a = cv<T>(ar[0]); b = cv<U>(ar[1]); }
    public void Multi<T, U, V>(out T a, out U b, out V c)
    { var ar = StrArr; a = cv<T>(ar[0]); b = cv<U>(ar[1]); c = cv<V>(ar[2]); }
    public void Multi<T, U, V, W>(out T a, out U b, out V c, out W d)
    { var ar = StrArr; a = cv<T>(ar[0]); b = cv<U>(ar[1]); c = cv<V>(ar[2]); d = cv<W>(ar[3]); }
    public void Multi<T, U, V, W, X>(out T a, out U b, out V c, out W d, out X e)
    { var ar = StrArr; a = cv<T>(ar[0]); b = cv<U>(ar[1]); c = cv<V>(ar[2]); d = cv<W>(ar[3]); e = cv<X>(ar[4]); }
    public void Multi<T, U, V, W, X, Y>(out T a, out U b, out V c, out W d, out X e, out Y f)
    { var ar = StrArr; a = cv<T>(ar[0]); b = cv<U>(ar[1]); c = cv<V>(ar[2]); d = cv<W>(ar[3]); e = cv<X>(ar[4]); f = cv<Y>(ar[5]); }
}
static class mymath
{
    public static long Mod = 1000000007;
    public static bool isprime(long a) {
        if (a < 2) return false;
        for (long i = 2; i * i <= a; i++) if (a % i == 0) return false;
        return true;
    }
    public static bool[] sieve(int n) {
        var p = new bool[n + 1];
        for (int i = 2; i <= n; i++) p[i] = true;
        for (int i = 2; i * i <= n; i++) if (p[i]) for (int j = i * i; j <= n; j += i) p[j] = false;
        return p;
    }
    public static List<int> getprimes(int n) {
        var prs = new List<int>();
        var p = sieve(n);
        for (int i = 2; i <= n; i++) if (p[i]) prs.Add(i);
        return prs;
    }
    public static long[][] E(int n) {
        var ret = new long[n][];
        for (int i = 0; i < n; i++) { ret[i] = new long[n]; ret[i][i] = 1; }
        return ret;
    }
    public static double[][] dE(int n) {
        var ret = new double[n][];
        for (int i = 0; i < n; i++) { ret[i] = new double[n]; ret[i][i] = 1; }
        return ret;
    }
    public static long[][] pow(long[][] A, long n) {
        if (n == 0) return E(A.Length);
        var t = pow(A, n / 2);
        if ((n & 1) == 0) return mul(t, t);
        return mul(mul(t, t), A);
    }
    public static double[][] pow(double[][] A, long n) {
        if (n == 0) return dE(A.Length);
        var t = pow(A, n / 2);
        if ((n & 1) == 0) return mul(t, t);
        return mul(mul(t, t), A);
    }
    public static double dot(double[] x, double[] y) {
        int n = x.Length;
        double ret = 0;
        for (int i = 0; i < n; i++) ret += x[i] * y[i];
        return ret;
    }
    public static double _dot(double[] x, double[] y) {
        int n = x.Length;
        double ret = 0, r = 0;
        for (int i = 0; i < n; i++) {
            double s = ret + (x[i] * y[i] + r);
            r = (x[i] * y[i] + r) - (s - ret);
            ret = s;
        }
        return ret;
    }
    public static long dot(long[] x, long[] y) {
        int n = x.Length;
        long ret = 0;
        for (int i = 0; i < n; i++) ret = (ret + x[i] * y[i]) % Mod;
        return ret;
    }
    public static T[][] trans<T>(T[][] A) {
        int n = A[0].Length, m = A.Length;
        var ret = new T[n][];
        for (int i = 0; i < n; i++) { ret[i] = new T[m]; for (int j = 0; j < m; j++) ret[i][j] = A[j][i]; }
        return ret;
    }
    public static double[] mul(double a, double[] x) {
        int n = x.Length;
        var ret = new double[n];
        for (int i = 0; i < n; i++) ret[i] = a * x[i];
        return ret;
    }
    public static long[] mul(long a, long[] x) {
        int n = x.Length;
        var ret = new long[n];
        for (int i = 0; i < n; i++) ret[i] = a * x[i] % Mod;
        return ret;
    }
    public static double[] mul(double[][] A, double[] x) {
        int n = A.Length;
        var ret = new double[n];
        for (int i = 0; i < n; i++) ret[i] = dot(x, A[i]);
        return ret;
    }
    public static long[] mul(long[][] A, long[] x) {
        int n = A.Length;
        var ret = new long[n];
        for (int i = 0; i < n; i++) ret[i] = dot(x, A[i]);
        return ret;
    }
    public static double[][] mul(double a, double[][] A) {
        int n = A.Length;
        var ret = new double[n][];
        for (int i = 0; i < n; i++) ret[i] = mul(a, A[i]);
        return ret;
    }
    public static long[][] mul(long a, long[][] A) {
        int n = A.Length;
        var ret = new long[n][];
        for (int i = 0; i < n; i++) ret[i] = mul(a, A[i]);
        return ret;
    }
    public static double[][] mul(double[][] A, double[][] B) {
        int n = A.Length;
        var Bt = trans(B);
        var ret = new double[n][];
        for (int i = 0; i < n; i++) ret[i] = mul(Bt, A[i]);
        return ret;
    }
    public static long[][] mul(long[][] A, long[][] B) {
        int n = A.Length;
        var Bt = trans(B);
        var ret = new long[n][];
        for (int i = 0; i < n; i++) ret[i] = mul(Bt, A[i]);
        return ret;
    }
    public static long[] add(long[] x, long[] y) {
        int n = x.Length;
        var ret = new long[n];
        for (int i = 0; i < n; i++) ret[i] = (x[i] + y[i]) % Mod;
        return ret;
    }
    public static long[][] add(long[][] A, long[][] B) {
        int n = A.Length;
        var ret = new long[n][];
        for (int i = 0; i < n; i++) ret[i] = add(A[i], B[i]);
        return ret;
    }
    public static long pow(long a, long b) {
        if (a >= Mod) return pow(a % Mod, b);
        if (a == 0) return 0;
        if (b == 0) return 1;
        var t = pow(a, b / 2);
        if ((b & 1) == 0) return t * t % Mod;
        return t * t % Mod * a % Mod;
    }
    public static long inv(long a) => pow(a, Mod - 2);
    public static long gcd(long a, long b) {
        while (b > 0) { var t = a % b; a = b; b = t; } return a;
    }
    // a x + b y = gcd(a, b)
    public static long extgcd(long a, long b, out long x, out long y) {
        long g = a; x = 1; y = 0;
        if (b > 0) { g = extgcd(b, a % b, out y, out x); y -= a / b * x; }
        return g;
    }
    public static long lcm(long a, long b) => a / gcd(a, b) * b;

    static long[] facts;
    public static long[] setfacts(int n) {
        facts = new long[n + 1];
        facts[0] = 1;
        for (int i = 0; i < n; i++) facts[i + 1] = facts[i] * (i + 1) % Mod;
        return facts;
    }
    public static long comb(int n, int r) {
        if (n < 0 || r < 0 || r > n) return 0;
        if (n - r < r) r = n - r;
        if (r == 0) return 1;
        if (r == 1) return n;
        if (facts != null && facts.Length > n) return facts[n] * inv(facts[r]) % Mod * inv(facts[n - r]) % Mod;
        int[] numer = new int[r], denom = new int[r];
        for (int k = 0; k < r; k++) { numer[k] = n - r + k + 1; denom[k] = k + 1; }
        for (int p = 2; p <= r; p++) {
            int piv = denom[p - 1];
            if (piv > 1) {
                int ofst = (n - r) % p;
                for (int k = p - 1; k < r; k += p) { numer[k - ofst] /= piv; denom[k] /= piv; }
            }
        }
        long ret = 1;
        for (int k = 0; k < r; k++) if (numer[k] > 1) ret = ret * numer[k] % Mod;
        return ret;
    }
    public static long[][] getcombs(int n) {
        var ret = new long[n + 1][];
        for (int i = 0; i <= n; i++) {
            ret[i] = new long[i + 1];
            ret[i][0] = ret[i][i] = 1;
            for (int j = 1; j < i; j++) ret[i][j] = (ret[i - 1][j - 1] + ret[i - 1][j]) % Mod;
        }
        return ret;
    }
    // nC0, nC2, ..., nCn
    public static long[] getcomb(int n) {
        var ret = new long[n + 1];
        ret[0] = 1;
        for (int i = 0; i < n; i++) ret[i + 1] = ret[i] * (n - i) % Mod * inv(i + 1) % Mod;
        return ret;
    }
}

Submission Info

Submission Time
Task F - Monochrome Cat
User riantkb
Language C# (Mono 4.6.2.0)
Score 800
Code Size 14684 Byte
Status AC
Exec Time 251 ms
Memory 44416 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 29 ms 9556 KB
0_001.txt AC 27 ms 9300 KB
0_002.txt AC 25 ms 11348 KB
0_003.txt AC 27 ms 11348 KB
1_003.txt AC 24 ms 9300 KB
1_004.txt AC 25 ms 11348 KB
1_005.txt AC 26 ms 11348 KB
1_006.txt AC 26 ms 9428 KB
1_007.txt AC 27 ms 13396 KB
1_008.txt AC 28 ms 11348 KB
1_009.txt AC 27 ms 9428 KB
1_010.txt AC 27 ms 11348 KB
1_011.txt AC 26 ms 9428 KB
1_012.txt AC 26 ms 9300 KB
1_013.txt AC 27 ms 11476 KB
1_014.txt AC 27 ms 13524 KB
1_015.txt AC 27 ms 11476 KB
1_016.txt AC 27 ms 11476 KB
1_017.txt AC 27 ms 11476 KB
1_018.txt AC 28 ms 13396 KB
1_019.txt AC 26 ms 9428 KB
1_020.txt AC 27 ms 11476 KB
1_021.txt AC 27 ms 11348 KB
1_022.txt AC 27 ms 11348 KB
1_023.txt AC 27 ms 11348 KB
1_024.txt AC 27 ms 11348 KB
1_025.txt AC 27 ms 11476 KB
1_026.txt AC 27 ms 11476 KB
1_027.txt AC 27 ms 13524 KB
1_028.txt AC 27 ms 9300 KB
1_029.txt AC 26 ms 9300 KB
1_030.txt AC 26 ms 9300 KB
1_031.txt AC 27 ms 9428 KB
1_032.txt AC 27 ms 13396 KB
1_033.txt AC 26 ms 9428 KB
1_034.txt AC 27 ms 11476 KB
1_035.txt AC 27 ms 11348 KB
1_036.txt AC 27 ms 13396 KB
1_037.txt AC 27 ms 11348 KB
1_038.txt AC 27 ms 13524 KB
1_039.txt AC 27 ms 11348 KB
1_040.txt AC 27 ms 11476 KB
1_041.txt AC 26 ms 11348 KB
1_042.txt AC 26 ms 11348 KB
1_043.txt AC 27 ms 11348 KB
1_044.txt AC 26 ms 9428 KB
1_045.txt AC 92 ms 27800 KB
1_046.txt AC 109 ms 30364 KB
1_047.txt AC 178 ms 27036 KB
1_048.txt AC 143 ms 24340 KB
1_049.txt AC 165 ms 32992 KB
1_050.txt AC 147 ms 27480 KB
1_051.txt AC 156 ms 27020 KB
1_052.txt AC 57 ms 18092 KB
1_053.txt AC 156 ms 26604 KB
1_054.txt AC 76 ms 19888 KB
1_055.txt AC 157 ms 28700 KB
1_056.txt AC 97 ms 23276 KB
1_057.txt AC 29 ms 9556 KB
1_058.txt AC 112 ms 25844 KB
1_059.txt AC 80 ms 19620 KB
1_060.txt AC 146 ms 22300 KB
1_061.txt AC 182 ms 33956 KB
1_062.txt AC 108 ms 27656 KB
1_063.txt AC 133 ms 25608 KB
1_064.txt AC 101 ms 23208 KB
1_065.txt AC 35 ms 14164 KB
1_066.txt AC 158 ms 27576 KB
1_067.txt AC 57 ms 17972 KB
1_068.txt AC 116 ms 19992 KB
1_069.txt AC 72 ms 18880 KB
1_070.txt AC 111 ms 21604 KB
1_071.txt AC 163 ms 25484 KB
1_072.txt AC 107 ms 23704 KB
1_073.txt AC 42 ms 14532 KB
1_074.txt AC 36 ms 14164 KB
1_075.txt AC 102 ms 19240 KB
1_076.txt AC 217 ms 30256 KB
1_077.txt AC 159 ms 25144 KB
1_078.txt AC 70 ms 16896 KB
1_079.txt AC 104 ms 22960 KB
1_080.txt AC 121 ms 21716 KB
1_081.txt AC 240 ms 35580 KB
1_082.txt AC 251 ms 37120 KB
1_083.txt AC 194 ms 27264 KB
1_084.txt AC 190 ms 27264 KB
1_085.txt AC 225 ms 44416 KB
1_086.txt AC 231 ms 37888 KB
1_087.txt AC 204 ms 29952 KB
1_088.txt AC 203 ms 27392 KB
1_089.txt AC 195 ms 30336 KB
1_090.txt AC 181 ms 26240 KB
1_091.txt AC 202 ms 29952 KB
1_092.txt AC 182 ms 26368 KB
1_093.txt AC 219 ms 32512 KB
1_094.txt AC 222 ms 38528 KB
1_095.txt AC 188 ms 27264 KB
1_096.txt AC 196 ms 29436 KB
1_097.txt AC 224 ms 34048 KB
1_098.txt AC 222 ms 31616 KB
1_099.txt AC 212 ms 27264 KB
1_100.txt AC 208 ms 30972 KB
1_101.txt AC 185 ms 27772 KB
1_102.txt AC 193 ms 27776 KB
1_103.txt AC 212 ms 31488 KB
1_104.txt AC 210 ms 28544 KB
1_105.txt AC 218 ms 31104 KB
1_106.txt AC 214 ms 28544 KB
1_107.txt AC 193 ms 25344 KB
1_108.txt AC 191 ms 25340 KB
1_109.txt AC 213 ms 28544 KB
1_110.txt AC 223 ms 26496 KB
1_111.txt AC 217 ms 27008 KB
1_112.txt AC 227 ms 28544 KB
1_113.txt AC 195 ms 31488 KB
1_114.txt AC 185 ms 25340 KB
1_115.txt AC 215 ms 30464 KB
1_116.txt AC 213 ms 28416 KB