Two-Colored Tree (Editorial)

Solution

Suppose we add a new edge between vertices $u$ and $v$.

Since the initial graph is a tree, the obtained cycle consists of the unique path from $u$ to $v$ in the tree and the newly added edge.

The weight of the new edge is $0$, so we only need to maximize the weight of the path from $u$ to $v$.

Let us understand when this path can be turned into a good cycle.

The colors of all edges on the path must alternate.

Also, the new edge is adjacent to both the first and the last edge of the path. Therefore, these two edges must have the same color, so that we can choose the opposite color for the new edge.

In an alternating path, the first and the last edges have the same color if and only if the number of edges is odd.

Therefore, the problem is equivalent to finding a maximum-weight path such that:

• the colors of its edges alternate;

• the number of edges in the path is odd.

Root the tree at vertex $1$.

For every vertex $v$, define dp[v][c][p] as the maximum weight of a downward alternating path which starts at $v$, whose first edge has color $c$, and whose number of edges has parity $p$.

Here c=0 denotes yellow, c=1 denotes blue, and p=0 means an even number of edges while p=1 means an odd number of edges.

Consider an edge from $v$ to its child $u$ with weight $w$ and color $c$.

We can create a path consisting only of this edge. Its length is odd, so

dp[v][c][1] = \max(dp[v][c][1],w).

We can also continue the path inside the subtree of $u$.

Since the colors must alternate, the first edge of the path starting from $u$ must have color c \oplus 1.

If such a path has parity $p$, then after adding the edge $(v,u)$ its parity changes to p\oplus 1.

Therefore,

dp[v][c][p\oplus 1] = \max(dp[v][c][p\oplus 1], w+dp[u][c\oplus 1][p]).

Now let us consider paths whose highest vertex is $v$.

Such a path can consist of only one downward part. In this case, we simply need its length to be odd, so both

dp[v][0][1]

and

dp[v][1][1]

are possible answers.

The path can also go from one child subtree through $v$ into another child subtree.

The two edges adjacent to $v$ must have different colors. Thus, one part starts with a yellow edge and the other one starts with a blue edge.

The total number of edges must be odd, so the parities of the two parts must be different.

Therefore, the two possible combinations are

dp[v][0][0]+dp[v][1][1]

and

dp[v][0][1]+dp[v][1][0].

Taking the maximum over all vertices gives the answer.

Notice that two parts with different first-edge colors necessarily use different edges from $v$, so they cannot belong to the same child subtree.

We process the vertices from leaves to the root.

The time complexity of the solution is $O(n)$.

The memory complexity is $O(n)$.

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define endl '\n'
#define pb push_back

const ll clasik = 2e5+17;
const ll INF = (1LL<<60);

struct edge {
    ll to , w , c;
};

vector<edge> g[clasik];

ll par[clasik];
ll dp[clasik][2][2];

signed main() {
    speed;

    ll n;

    cin>>n;

    for (int i = 1 ; i<n ; i++) {
        ll u , v , w;
        char c;

        cin>>u>>v>>w>>c;

        ll col = (c == 'B');

        g[u].pb({v , w , col});
        g[v].pb({u , w , col});
    }

    vector<ll> order;
    vector<ll> st;

    par[1] = 0;
    st.pb(1);

    while(!st.empty()) {
        ll v = st.back();
        st.pop_back();

        order.pb(v);

        for (auto e : g[v]) {
            if (e.to == par[v]) continue;

            par[e.to] = v;
            st.pb(e.to);
        }
    }

    for (int v = 1 ; v<=n ; v++) {
        for (int c = 0 ; c<2 ; c++) {
            for (int p = 0 ; p<2 ; p++) {
                dp[v][c][p] = -INF;
            }
        }
    }

    reverse(order.begin() , order.end());

    ll ans = 0;

    for (auto v : order) {

        for (auto e : g[v]) {
            ll u = e.to;

            if (par[u] != v) continue;

            ll c = e.c;
            ll w = e.w;

            dp[v][c][1] = max(dp[v][c][1] , w);

            for (int p = 0 ; p<2 ; p++) {
                if (dp[u][c^1][p] == -INF) continue;

                dp[v][c][p^1] =
                    max(dp[v][c][p^1] , w + dp[u][c^1][p]);
            }
        }

        ans = max(ans , dp[v][0][1]);
        ans = max(ans , dp[v][1][1]);

        if (dp[v][0][0] != -INF && dp[v][1][1] != -INF) {
            ans = max(ans , dp[v][0][0] + dp[v][1][1]);
        }

        if (dp[v][0][1] != -INF && dp[v][1][0] != -INF) {
            ans = max(ans , dp[v][0][1] + dp[v][1][0]);
        }
    }

    cout<<ans<<endl;

    return 0;
}