Educational Codeforces 035 div.2 F. Tree Destruction

Educational Codeforces 035 div.2 F. Tree Destruction

Problem - F - Codeforces

解法

まず直径をできるだけ残しておくべきであることがわかります。なぜなら、直径を残している間は、それ以外の辺を破壊していくときに、その辺を破壊したときに得られる最大スコアを得ることができるからです。

直径以外の辺は、破壊の度にその辺を破壊したときに得られる最大スコアを得られることから、題意に矛盾しない順序であれば任意の順番で破壊してよいです。

最後に直径を端から崩していけばよいです。

直径のパスが、複数ありうる場合はどれを使っても良いことを示します。

ある二つのパスがともに直径になっているとします。これはいずれも中心の点（辺）を通っているはずで、ある点から分岐しているものと考えられます。この分岐している部分のパスの各頂点から直径の反対側の点までの距離の総和は等しいので、これらを破壊するときに得られるスコアは等しいです。よって示されました。

実際に出力するのは、破壊する辺の片方の頂点と、そこから最も遠い位置にある頂点です。こちらはLCAなどで高速に求めることができます。

直径のパスを一つ挙げる実装を書くのが微妙にめんどうだったのでライブラリ化しました。

実装

#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;

vector<int> DiameterPath(const vector<vector<int>> &g) {
        int n = g.size();
        if (n == 1) return vector<int> { 0 };

        //find the farthest point from the start
        auto farthest = [&](int start) {
                vector<int> depth(n);
                function<void (int, int, int)> get_depth = [&](int u, int prev, int d) {
                        depth[u] = d;
                        for (auto v : g[u]) if (v != prev) {
                                get_depth(v, u, d + 1);
                        }
                };
                get_depth(start, -1, 0);
                int maxd = 0;
                int res = 0;
                for (int i = 0; i < n; i ++) {
                        if (depth[i] > maxd) {
                                maxd = depth[i];
                                res = i;
                        }
                }
                return res;
        };

        //get end points
        int s = farthest(0);
        int t = farthest(s);

        //construct a diameter path
        vector<int> diameter_path;
        function<void (int, int, vector<int> &)> construct = [&](int u, int prev, vector<int> &path) {
                if (u == t) {
                        diameter_path = path;
                        return;
                }
                for (auto v : g[u]) if (v != prev) {
                        path.push_back(v);
                        construct(v, u, path);
                        path.pop_back();
                }
        };
        vector<int> tmp;
        tmp.push_back(s);
        construct(s, -1, tmp);

        return diameter_path;
}

//LCA
const int LOGM = 30;
vector<int> lca_depth;
vector<vector<int>> parent(LOGM);
void lca_init(int root, const vector<vector<int>> &g) {
        int n = g.size();
        lca_depth.resize(n);
        for (int i = 0; i < LOGM; i ++) parent[i].resize(n);
        function<void (int, int, int)> dfs = [&](int u, int prev, int d) {
                parent[0][u] = prev;
                lca_depth[u] = d;
                for (auto v : g[u]) if (v != prev) dfs(v, u, d + 1);
        };
        dfs(root, -1, 0);
        for (int k = 0; k < LOGM - 1; k ++) {
                for (int i = 0; i < n; i ++) {
                        if (parent[k][i] < 0) parent[k + 1][i] = -1;
                        else parent[k + 1][i] = parent[k][parent[k][i]];
                }
        }
}
int lca(int u, int v) { 
        if (lca_depth[u] > lca_depth[v]) swap(u, v);
        for (int k = 0; k < LOGM; k ++) {
                if ((lca_depth[v] - lca_depth[u]) >> k & 1) { 
                        v = parent[k][v];
                }
        }
        if (u == v) return u;
        for (int k = LOGM - 1; k >= 0; k --) {
                if (parent[k][u] != parent[k][v]) {
                        u = parent[k][u];
                        v = parent[k][v];
                }
        }
        return parent[0][u];
}
int lca_dist(int u, int v) {
        return lca_depth[u] + lca_depth[v] - 2 * lca_depth[lca(u, v)];
}
//

int main() {
        int n;
        scanf(&quot;%d&quot;, &n);
        vector<vector<int>> g(n);
        for (int i = 0; i < n - 1; i ++) {
                int a, b;
                scanf(&quot;%d%d&quot;, &a, &b);
                a --, b --;
                g[a].push_back(b);
                g[b].push_back(a);
        }
        lca_init(0, g);
        auto path = DiameterPath(g);
        int s = path.front(), t = path.back();
        long long sum = 0;
        vector<bool> used(n, false);
        vector<int> to;
        for (int i = 0; i < path.size(); i ++) {
                used[path[i]] = true;
                if (i > 0) to.push_back(path[i]);
        }
        int meter = path.size() - 1;
        sum += (long long) meter * (meter + 1) / 2;
        function<void (int, int)> dfs = [&](int u, int prev) {
                for (auto v : g[u]) if (v != prev) {
                        if (!used[v]) { 
                                sum += max(lca_dist(v, s), lca_dist(v, t));
                                to.push_back(v);
                        }
                        dfs(v, u);
                }
        };
        dfs(s, -1);
        printf(&quot;%lld\n&quot;, sum);
        bool on_path = false;
        for (int i = n - 2; i >= 0; i --) {
                int v = to[i];
                if (v == t) on_path = true;
                if (on_path) {
                        printf(&quot;%d %d %d\n&quot;, s + 1, v + 1, v + 1);
                } else {
                        if (lca_dist(v, s) > lca_dist(v, t)) {
                                printf(&quot;%d %d %d\n&quot;, s + 1, v + 1, v + 1);
                        } else {
                                printf(&quot;%d %d %d\n&quot;, t + 1, v + 1, v + 1);
                        }
                }
        }
        return 0;
}