Двокольорове дерево (Розбір)

Розв'язання

Припустимо, що ми додаємо нове ребро між вершинами $u$ та $v$.

Оскільки початковий граф є деревом, утворений цикл складається з єдиного шляху між $u$ та $v$ у дереві та нового доданого ребра.

Вага нового ребра дорівнює $0$, тому нам потрібно максимізувати лише вагу шляху між $u$ та $v$.

З'ясуємо, коли такий шлях можна доповнити до хорошого циклу.

Кольори всіх ребер на шляху повинні чергуватися.

Також нове ребро буде сусіднім одночасно з першим і останнім ребрами шляху. Тому перше та останнє ребра шляху повинні мати однаковий колір, щоб для нового ребра можна було вибрати протилежний колір.

В alternating-шляху перше та останнє ребра мають однаковий колір тоді й лише тоді, коли кількість ребер у шляху непарна.

Отже, задача еквівалентна знаходженню шляху максимальної ваги, для якого виконуються дві умови:

• кольори ребер на шляху чергуються;

• кількість ребер у шляху непарна.

Вкорінимо дерево у вершині $1$.

Для кожної вершини $v$ визначимо

dp[v][c][p]

як максимальну вагу спрямованого вниз alternating-шляху, який починається у вершині $v$, перше ребро якого має колір $c$, а парність кількості ребер дорівнює $p$.

Тут c=0 означає жовтий колір, c=1 — блакитний, p=0 означає парну кількість ребер, а p=1 — непарну.

Розглянемо ребро з вершини $v$ до її сина $u$ з вагою $w$ та кольором $c$.

Ми можемо побудувати шлях, що складається лише з цього ребра. Його довжина непарна, тому

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

Також ми можемо продовжити шлях у піддереві вершини $u$.

Оскільки кольори повинні чергуватися, перше ребро шляху, який починається у $u$, повинно мати колір c \oplus 1.

Якщо такий шлях має парність $p$, то після додавання ребра $(v,u)$ його парність зміниться на p\oplus 1.

Тому

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

Тепер розглянемо шляхи, найвища вершина яких дорівнює $v$.

Такий шлях може складатися лише з однієї спрямованої вниз частини. У цьому випадку його довжина повинна бути непарною, тому кандидатами на відповідь є

dp[v][0][1]

та

dp[v][1][1].

Також шлях може йти з одного піддерева через вершину $v$ в інше піддерево.

Два ребра, сусідні з $v$, повинні мати різні кольори. Отже, одна частина починається з жовтого ребра, а інша — з блакитного.

Загальна кількість ребер у шляху повинна бути непарною, тому парності двох частин повинні відрізнятися.

Отже, маємо два можливі варіанти:

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

та

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

Беручи максимум серед усіх вершин, отримаємо відповідь.

Зауважимо, що дві частини з різними кольорами першого ребра обов'язково використовують різні ребра, що виходять з $v$, тому вони не можуть проходити через одного й того самого сина.

Обробляємо вершини у порядку від листків до кореня.

Часова складність розв'язання — $O(n)$.

Просторова складність — $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;
}