Розв’язання

Маємо дерево з $n$ вершин, запускаємо обхід dfs(1). У кожній вершині порядок перебору дітей дозволено обирати довільно, отже ми можемо впливати на порядок відвідування вершин, а значить і на рядок, який утвориться при виписуванні номерів вершин у порядку обходу (без роздільників).

Нехай цей рядок цифр — це $x$. Функція $F(x)$ дорівнює довжині найбільшого підрядка в $x$, який складається лише з цифр $1$ та $7$. Потрібно максимізувати $F(x)$, вибираючи порядок DFS.

1. Локальні характеристики вершини

Для вершини $v$ розглянемо її десятковий запис s_v.

Визначимо:

• pref_v — довжина найбільшого префікса s_v, що складається тільки з цифр $1$ та $7$;

• suff_v — довжина найбільшого суфікса s_v, що складається тільки з цифр $1$ та $7$;

• вершина є повністю доброю, якщо pref_v = |s_v| (тобто всі цифри — $1$ або $7$).

Підрядок з одних $1/7$ не може «перестрибнути» через погану цифру всередині s_v, тому при злитті частин обходу для різних піддерев важливими є саме ці три характеристики: чи можемо зробити увесь шматок добрим, або максимальні добрі префікс/суфікс.

2. DP-стани

Зафіксуємо корінь у вершині $1$. Для кожної вершини $v$ (під час DFS із батьком $p$) розглядаємо рядок S_v, який утвориться з піддерева $v$ у порядку DFS (не заходячи в $p$).

Заведемо:

• $\text{dp[v][0]}$ — довжина S_v, якщо можна вибрати порядок обходу так, що весь S_v складається лише з $1/7$; якщо неможливо — $-\infty$;

• $\text{dp[v][1]}$ — максимальна довжина доброго префікса S_v серед усіх порядків обходу;

• $\text{dp[v][2]}$ — максимальна довжина доброго суфікса S_v серед усіх порядків обходу.

Також підтримуємо глобальну відповідь ans — максимум $F(x)$, який можна отримати.

3. Об’єднання дітей

Нехай у вершини $v$ є діти to. Розіб’ємо їх:

• добрі діти — ті, для яких \texttt{dp[to][0]} \neq -\infty (їх піддерево можна зробити повністю з $1/7$);

• погані — решта.

Позначимо: [ sum = pref_v + _to — добрий dp[to][0]. ] Це максимальна «добра» довжина, яку можемо гарантовано зібрати на початку, якщо спочатку відвідати вершину $v$ (її добрий префікс), а потім усі повністю добрі піддерева.

Для поганих дітей корисні: [ mx = dp[to][1],  mx0 = dp[to][2] ] (максимальні префікс та суфікс серед поганих піддерев).

4. Формули переходів

• Повністю добрий фрагмент: він існує тоді й лише тоді, коли $v$ повністю добра і всі діти повністю добрі: [ dp[v][0] = sum, ] інакше dp[v][0] = -\infty.

• Найкращий префікс: якщо число $v$ повністю добре, можна взяти $sum$ і зайти у найкращий префікс одного поганого піддерева: [ dp[v][1] = (pref_v,; sum + mx). ] Якщо $v$ не повністю добре, то глибше все одно не можна продовжити префікс через «погану» цифру всередині s_v, тому базово маємо pref_v.

• Найкращий суфікс: нехай G = sum - pref_v — сума довжин усіх повністю добрих дітей. Тоді: [ dp[v][2] =

  G + suff_v, якщо немає поганих дітей,

  G + mx0, інакше.

  ]

5. Оновлення глобальної відповіді

Найкращий підрядок з $1/7$ може:

• складатися лише з повністю добрих піддерев дітей: $G$;

• починатися в суфіксі $v$, пройти всі повністю добрі піддерева і зайти в префікс одного поганого: suff_v + G + mx;

• починатися в одному поганому піддереві та закінчуватися в іншому, а між ними стоять усі повністю добрі: для цього перебираємо поганих дітей і тримаємо два максимуми вже бачених: pref2 (кращий суфікс) і pref1 (кращий префікс), оновлюючи: [ ans = (ans,; G + dp[to][1] + pref2), ] [ ans = (ans,; G + dp[to][2] + pref1). ]

6. Складність

Кожне ребро переглядається $O(1)$ разів у DFS, а всі оновлення по дітях — сумарно $O(n)$. Отже: [ часова складність O(n),  пам’ять O(n). ]

Код розв’язку

//#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;
template<class T>
using vec = vector<T>;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef KoRoVa
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define DEBUG while (false)
#define LOG(...)
#endif

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

vector <int> edge[max_n];

int dp[max_n][3];

// 0 - full
// 1 - pref

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;
            umax(mx, dp[to][1]);
            umax(mx0, dp[to][2]);
        }
        else {
            sum += dp[to][0];
        }
    }
    if (full) {
        dp[v][0] = sum;
    }
    if (pref == len(cur)) {
        dp[v][1] = sum + mx;
    }
    umax(dp[v][1], pref);
    if (!bad) {
        dp[v][2] = sum - pref + suff;
    }
    else {
        dp[v][2] = sum - pref + mx0;
    }
    umax(ans, sum - pref);
    umax(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;
        }
        umax(ans, sum - pref + dp[to][1] + pref2);
        umax(ans, sum - pref + dp[to][2] + pref1);
        umax(pref2, dp[to][2]);
        umax(pref1, dp[to][1]);
    }
    LOG(v, ans);

}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    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++) {
        umax(ans, dp[i][0]);
        umax(ans, dp[i][1]);
        umax(ans, dp[i][2]);
    }
    cout << ans << '\n';
}

/*
KoRoVa!
*/