提出 #54180865

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define mp make_pair
#define all(x) x.begin(), x.end()
#define x first
#define y second

vector<int> adj[202020];
int dp[4][202020];
// portal 사용 / 미사용
// 왕복   0   1
// 일방   2   3 

int ans;
void dfs(int v, int pv = -1) {

    for (int i = 0; i < 4; i++) dp[i][v] = 0;
    int mn = 0;
    int mn2 = 0;

    for (auto f : adj[v]) if (f != pv) {
        dfs(f, v);
        dp[1][v] += dp[1][f] + 2;
        dp[3][v] += dp[1][f] + 2;
        mn = min(mn, -dp[1][f] - 1 + dp[3][f]);

        int val = min(dp[3][f] + 1, dp[0][f] + 2);
        dp[0][v] += val;
        dp[2][v] += val;
        mn2 = min(mn2, -val + dp[2][f] + 1);
    }

    dp[3][v] += mn;
    dp[2][v] += mn2;

    /*cout << "R1: " << v << " | ";
    for (int i = 0; i < 4; i++) cout << dp[i][v] << ' ';
    cout << '\n';*/
}

void dfs2(int v, int pv = -1, vector<int> p = { 0, 0, 0, 0 }) {

    vector<pair<int, int>> mn, mn2;
    
    mn.push_back(mp(0, 0));
    mn2.push_back(mp(0, 0));
    vector<int> ndp(4);
    for (auto f : adj[v]) if (f != pv) {
        ndp[1] += dp[1][f] + 2;
        ndp[3] += dp[1][f] + 2;
        mn.push_back(mp(-dp[1][f] - 1 + dp[3][f], f));
        int val = min(dp[3][f] + 1, dp[0][f] + 2);
        ndp[0] += val;
        ndp[2] += val;
        mn2.push_back(mp(-val + dp[2][f] + 1, f));
    }

    if (pv != -1) {
        ndp[1] += p[1] + 2;
        ndp[3] += p[1] + 2;
        mn.push_back(mp(-p[1] - 1 + p[3], pv));
        int val = min(p[3] + 1, p[0] + 2);
        ndp[0] += val;
        ndp[2] += val;
        mn2.push_back(mp(-val + p[2] + 1, pv));
    }
    sort(all(mn));
    sort(all(mn2));

   // cout << "R2: " << v << " | ";
    for (int i = 0; i < 4; i++) {
        if (i == 3) {
            ans = min(ans, ndp[i] + mn[0].x);
            //cout << ndp[i] + mn[0].x << ' ';
        }
        else if (i == 2) {
            ans = min(ans, ndp[i] + mn2[0].x);
          //  cout << ndp[i] + mn2[0].x << ' ';
        }
        else {
            ans = min(ans, ndp[i]);
            //cout << ndp[i] << ' ';
        }
    }
   /* cout << '\n';
    cout << "UPP: ";
    for (auto f : p) cout << f << ' ';
    cout << '\n';*/

    for (auto f : adj[v]) if (f != pv) {

        vector<int> np(4);

        np[1] = ndp[1] - (dp[1][f] + 2);
        np[3] = ndp[3] - (dp[1][f] + 2);
        for (int i = 0; i < 2; i++) {
            if (mn[i].y == f) continue;
            np[3] += mn[i].x;
            break;
        }

        int val = min(dp[3][f] + 1, dp[0][f] + 2);
        np[0] = ndp[0] - val;
        np[2] = ndp[2] - val;
        for (int i = 0; i < 2; i++) {
            if (mn2[i].y == f) continue;
            np[2] += mn2[i].x;
            break;
        }
        dfs2(f, v, np);
    }

}

void solve() {
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    ans = n * 10;

    dfs(1);
    dfs2(1);
    cout << ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t = 1;
    // cin >> t;
    while (t--) solve();
}

提出情報

ジャッジ結果