提出 #39635471

---

ソースコード 拡げる

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
typedef long long ll;
using namespace std;
const int maxn = 2e5 + 5;
const int maxlog = 30;
const int inf = 0x3f3f3f3f;
int n, f[maxn][3][maxlog + 1], tmp[3][maxlog + 1];
vector<int> e[maxn];
void ckmin(int &x, int y) {
    x = y < x ? y : x;
}
void dfs(int u, int from) {
    f[u][0][1] = f[u][1][1] = f[u][2][1] = 1;
    for(int v : e[u]) {
        if(v == from) {
            continue;
        }
        dfs(v, u);
        memset(tmp, 0x3f, sizeof(tmp));
        for(int x = 0; x < 3; x++) {
            for(int i = 0; i <= maxlog; i++) {
                if(f[u][x][i] == inf) {
                    continue;
                }
                for(int y = 0; y < 3; y++) {
                    for(int j = 0; j <= maxlog; j++) {
                        int need = max(f[u][x][i], f[v][y][j]);
                        if(j < maxlog) {
                            ckmin(tmp[x][max(i, j + 1)], max(i + j, need));
                        }
                        if(x < 2 && y < 2) {
                            ckmin(tmp[x + 1][max(i, j)], max(i + j - 1, need));
                        }
                    }
                }
            }
        }
        for(int o = 0; o < 3; o++) {
            for(int i = 0; i <= maxlog; i++) {
                f[u][o][i] = tmp[o][i];
            }
        }
    }
}
int main() {
#ifdef DEBUG
	freopen("1.in", "r", stdin);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
    cin >> n;
    for(int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        e[u].eb(v);
        e[v].eb(u);
    }
    memset(f, 0x3f, sizeof(f));
    dfs(1, 0);
    int ans = inf;
    for(int i = 0; i <= maxlog; i++) {
        ckmin(ans, f[1][2][i]);
    }
    cout << ans << '\n';
	return 0;
}

提出情報

ジャッジ結果