Problem: There is a tree with N vertices numbered 1 through N. The i-th edge connects Vertex x_i and y_i. Each vertex is painted white or black. The initial color of Vertex i is represented by a letter c_i. c_i = `W` represents the vertex is white; c_i = `B` represents the vertex is black.  A cat will walk along this tree. More specifically, she performs one of the following in one second repeatedly:    * Choose a vertex that is adjacent to the vertex where she is currently, and move to that vertex. Then, invert the color of the destination vertex.   * Invert the color of the vertex where she is currently.  The cat's objective is to paint all the vertices black. She may start and end performing actions at any vertex. At least how many seconds does it takes for the cat to achieve her objective?

Submission attempts (in order):
def first_cut(links, colors):
    tmp_links = links.copy()
    for v, neighbors in tmp_links.items():
        while len(neighbors) == 1 and colors[v]:
            del links[v]
            par = neighbors.pop()
            links[par].remove(v)
            v = par
            neighbors = links[par]
    return links


def solve(links, colors):
    ans = 0
    if all(colors):
        return 0

    print(links)
    links = first_cut(links, colors)
    print(links)

    while True:
        if len(links) == 1:
            col = [colors[i] for i in links][0]
            if col:
                pass
            else:
                ans -= 1
            return ans
        if len(links) == 2:
            col = [colors[i] for i in links]
            if all(col):
                pass
            elif any(col):
                ans += 1
            else:
                ans += 2
            return ans

        tmp_links = links.copy()

        for v, neighbors in tmp_links.items():
            if len(neighbors) > 1 or not neighbors:
                continue
            if colors[v]:
                ans += 1
            else:
                ans += 2
            par = neighbors.pop()
            colors[par] ^= 1
            links[par].remove(v)
            del links[v]


n = int(input())
links = {i: set() for i in range(n)}
for _ in range(n - 1):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    links[x].add(y)
    links[y].add(x)
colors = [c == 'B' for c in input()]

print(solve(links, colors))


from collections import deque


def first_cut(links, colors):
    tmp_links = links.copy()
    for v, neighbors in tmp_links.items():
        while len(neighbors) == 1 and colors[v]:
            del links[v]
            par = neighbors.pop()
            links[par].remove(v)
            v = par
            neighbors = links[par]
    return links


def diameter(links, flags):
    def dfs(s):
        fs = flags[s]
        d, v = 0, 0
        q = deque(sorted((fs + flags[v], v, s) for v in links[s]))
        while q:
            d, v, a = q.popleft()
            for u in links[v]:
                if u == a:
                    continue
                fu = flags[u]
                if fu:
                    q.append((d + 1, u, v))
                else:
                    q.appendleft((d, u, v))
        return d, v

    s = next(iter(links))
    _, t = dfs(s)
    d, _ = dfs(t)
    return d


def solve(links, colors):
    if all(colors):
        return 0

    links = first_cut(links, colors)
    k = len(links)

    if k == 1:
        return 1

    flags = {v: colors[v] ^ (len(link) % 2 == 0) for v, link in links.items()}
    euler_tour = 2 * (k - 1) + sum(flags.values())
    return euler_tour - 2 * diameter(links, flags)


n = int(input())
links = {i: set() for i in range(n)}
for _ in range(n - 1):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    links[x].add(y)
    links[y].add(x)
colors = [c == 'B' for c in input()]

print(solve(links, colors))


Verdicts: Wrong Answer

Accepted