Submission #254811

#	Time	Username	Problem	Language	Result	Execution time	Memory
254811		imeimi2000	Village (BOI20_village)	C++17	100 / 100	143 ms	21616 KiB

Village

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> edge[100001];

namespace solve1 {
    int dp[100001][2], pr[100001];
    void dfs(int x, int p) {
        dp[x][0] = 0;
        dp[x][1] = 1;
        int mn = 1e8;
        for (int i : edge[x]) {
            if (i == p) continue;
            dfs(i, x);
            int val = min(dp[i][0], dp[i][1]);
            if (dp[i][1] - val < mn) mn = dp[i][1] - val, pr[x] = i;
            dp[x][0] += val;
            dp[x][1] += val;
        }
        dp[x][0] += mn;
    }

    vector<int> lst[100001];
    int g[100001];
    void dfs2(int x, int p, int j) {
        if (j) lst[g[x] = g[p]].push_back(x);
        else lst[g[x] = x].push_back(x);
        for (int i : edge[x]) {
            if (i == p) continue;
            if (j) {
                dfs2(i, x, dp[i][0] > dp[i][1]);
            }
            else {
                dfs2(i, x, i == pr[x] || dp[i][0] > dp[i][1]);
            }
        }
    }
    int ans[100001];
    long long solve() {
        dfs(1, 0);
        dfs2(1, 0, 0);
        for (int i = 1; i <= n; ++i) {
            int sz = lst[i].size();
            if (!sz) continue;
            for (int j = 0; j < sz; ++j) {
                ans[lst[i][j]] = lst[i][(j + 1) % sz];
            }
        }
        return dp[1][0] * 2;
    }
    void print() {
        for (int i = 1; i <= n; ++i) {
            printf("%d%c", ans[i], "\n "[i < n]);
        }
    }
}

namespace solve2 {
    int sz[100001];

    void dfs(int x, int p) {
        sz[x] = 1;
        for (int i : edge[x]) {
            if (i == p) continue;
            dfs(i, x);
            sz[x] += sz[i];
        }
    }

    vector<int> lst;
    long long sum = 0;
    void dfs2(int x, int p, int d = 0) {
        lst.push_back(x);
        sum += d;
        for (int i : edge[x]) {
            if (i == p) continue;
            dfs2(i, x, d + 1);
        }
    }

    int ans[100001];
    long long solve() {
        dfs(1, 0);
        int x = 1;
        for (int p = 0, loop = 1; loop; ) {
            loop = 0;
            for (int i : edge[x]) {
                if (i == p) continue;
                if (sz[i] * 2 > n) {
                    p = x;
                    x = i;
                    loop = 1;
                    break;
                }
            }
        }
        dfs2(x, 0);
        for (int i = 0; i < n; ++i) {
            ans[lst[i]] = lst[(i + n / 2) % n];
        }
        return sum * 2;
    }
    void print() {
        for (int i = 1; i <= n; ++i) {
            printf("%d%c", ans[i], "\n "[i < n]);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    printf("%lld %lld\n", solve1::solve(), solve2::solve());
    solve1::print();
    solve2::print();
    return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 38 / 38
• Subtask 3: 50 / 50