Qızılgüllər və DFS#12287

Qızılgüllər və DFS (Həll təhlili)

Məsələnin müəllifi:	Andrey Xolod (Connect)
Hazırlayan:	Andrey Xolod (Connect)
Təhlil:	Andrey Xolod (Connect)

Həll

Bizə $n$ zirvədən ibarət bir ağac verilir və dfs(1) başladılır. Hər zirvədə uşaqların keçilmə ardıcıllığını istədiyimiz kimi seçə bildiyimiz üçün, zirvələrin ziyarət olunma qaydasına təsir edə bilirik. Deməli, ziyarət olunan zirvələrin ardıcıl yazılması ilə alınan sətirə də təsir etmiş oluruq.

Bu sətir $x$ olsun. Funksiyası $F (x)$ — yalnız 1 və 7 rəqəmlərindən ibarət olan ən uzun alt-sətrin uzunluğudur. Məqsəd — DFS ardıcıllığını elə seçməkdir ki, $F (x)$ maksimum olsun.

1. Zirvənin lokal xarakteristikaları

Zirvə $v$ üçün onun onluq yazılışı $s_{v}$ s_v-ni nəzərə alaq.

Təyin edirik:

$p r e f_{v}$ pref_v — $s_{v}$ s_v-nin yalnız $1$ və $7$ rəqəmlərindən ibarət olan maksimal prefiksinin uzunluğu;
$s u f f_{v}$ suff_v — $s_{v}$ s_v-nin yalnız $1$ və $7$ rəqəmlərindən ibarət olan maksimal suffiksinin uzunluğu;
zirvə tam yaxşıdır, əgər $p r e f_{v} = ∣ s_{v} ∣$ pref_v = |s_v| (yəni bütün rəqəmlər $1$ və ya $7$ -dir).

Yalnız $1/7$ -lərdən ibarət olan alt-sətir $s_{v}$ s_v daxilindəki pis rəqəmi “atlayıb keçə bilməz”. Ona görə də pod-ağacların birləşdirilməsi zamanı bu üç parametr əsas rol oynayır.

2. DP vəziyyətləri

Ağacın kökü $1$ -ci zirvə olsun. Hər zirvə $v$ üçün (DFS zamanı) onun pod-ağacı üzrə alınan sətir $S_{v}$ S_v-ni nəzərə alaq.

Aşağıdakıları təyin edirik:

$dp[v][0]$ — əgər uşaqların keçilmə ardıcıllığını elə seçmək mümkündürsə ki, $S_{v}$ S_v-nin hamısı yalnız $1/7$ -lərdən ibarət olsun, onda onun uzunluğu; əks halda $- \infty$ ;
$dp[v][1]$ — $S_{v}$ S_v üçün mümkün olan ən böyük yaxşı prefiksin uzunluğu;
$dp[v][2]$ — $S_{v}$ S_v üçün mümkün olan ən böyük yaxşı suffiksin uzunluğu.

Qlobal dəyişən ans ən yaxşı nəticəni saxlayır.

3. Uşaqların birləşdirilməsi

Zirvə $v$ -nin uşaqları to olsun. Onları iki hissəyə ayıraq:

yaxşı uşaqlar — $dp[to][0] \neq = - \infty$ \texttt{dp[to][0]} \neq -\infty olanlar;
pis uşaqlar — qalanlar.

Belə təyin edirik: [ sum = pref_v + _to — yaxşı dp[to][0]. ]

Pis uşaqlar üçün: [ mx = dp[to][1], mx0 = dp[to][2]. ]

4. Keçid formulları

Tam yaxşı fraqment: Bu ancaq o halda mümkündür ki, həm $v$ tam yaxşı olsun, həm də bütün uşaqlar yaxşı olsun: [ dp[v][0] = sum. ] Əks halda $d p [v] [0] = - \infty$ dp[v][0] = -\infty.
Ən yaxşı prefiks: Əgər $v$ tam yaxşıdırsa: [ dp[v][1] = (pref_v,; sum + mx). ] Əgər deyil — prefiks $p r e f_{v}$ pref_v ilə məhdudlaşır.
Ən yaxşı suffiks: $G = s u m - p r e f_{v}$ G = sum - pref_v olsun. Onda: [ dp[v][2] =
G + suff_v, pis uşaq yoxdursa,
G + mx0, əks halda.
]

5. Qlobal cavabın yenilənməsi

Ən uzun $1/7$ alt-sətiri aşağıdakı hallarda yaranır:

yalnız yaxşı uşaqlardan ibarət olduqda: $G$ ;
$v$ -nin suffiksindən başlayıb yaxşı uşaqlardan keçərək bir pis uşağın prefiksinə daxil olduqda: [ suff_v + G + mx; ]
iki pis uşağın arasında, yaxşı uşaqların isə ortada olduğu halda.
Bu halda pis uşaqları ardıcıl nəzərdən keçirib iki maksimum saxlanılır: pref1 və pref2. Cavab aşağıdakı kimi yenilənir: [ ans = (ans,; G + dp[to][1] + pref2), ] [ ans = (ans,; G + dp[to][2] + pref1). ]

6. Mürəkkəblik

Hər kənar $O (1)$ dəfə emal olunur. Ümumi mürəkkəblik: [ O(n) vaxt, O(n) yaddaş. ]

Həllin kodu

//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#include <bits/stdc++.h>

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

const int max_n = 2e5 + 11, inf = 1000111222;

vector <int> edge[max_n];

int dp[max_n][3];

int good (int x) {
    return x == 1 || x == 7;
}

int ans = 0;

void dfs (int v, int p = -1) {
    dp[v][0] = -inf;
    dp[v][1] = -inf;
    dp[v][2] = -inf;
    int x = v + 1;
    int pref = 0, suff = 0;
    vector <int> cur;
    while (x) {
        cur.pb(x % 10);
        x /= 10;
    }
    while (pref < len(cur) && good(cur[len(cur) - 1 - pref])) ++pref;
    while (suff < len(cur) && good(cur[suff])) ++suff;

    int full = pref == len(cur), sum = pref, mx = 0, mx0 = 0;
    bool bad = false;

    for (int to : edge[v]) {
        if (to == p) continue;
        dfs(to, v);
        if (dp[to][0] == -inf) {
            full = 0;
            bad = true;
            mx = max(mx, dp[to][1]);
            mx0 = max(mx0, dp[to][2]);
        } else {
            sum += dp[to][0];
        }
    }

    if (full) dp[v][0] = sum;

    if (pref == len(cur)) dp[v][1] = sum + mx;
    dp[v][1] = max(dp[v][1], pref);

    if (!bad) dp[v][2] = sum - pref + suff;
    else dp[v][2] = sum - pref + mx0;

    ans = max(ans, sum - pref);
    ans = max(ans, suff + sum - pref + mx);

    int pref2 = 0, pref1 = 0;
    for (int to : edge[v]) {
        if (to == p) continue;
        if (dp[to][0] != -inf) continue;

        ans = max(ans, sum - pref + dp[to][1] + pref2);
        ans = max(ans, sum - pref + dp[to][2] + pref1);

        pref2 = max(pref2, dp[to][2]);
        pref1 = max(pref1, dp[to][1]);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;

    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        --u, --v;
        edge[u].pb(v);
        edge[v].pb(u);
    }

    dfs(0);

    for (int i = 0; i < n; i++) {
        ans = max(ans, dp[i][0]);
        ans = max(ans, dp[i][1]);
        ans = max(ans, dp[i][2]);
    }

    cout << ans << '\n';
}

C++