結果

問題 No.1976 Cut then Connect
ユーザー 👑 emthrmemthrm
提出日時 2022-06-10 23:49:33
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 7,762 bytes
コンパイル時間 2,273 ms
コンパイル使用メモリ 208,408 KB
最終ジャッジ日時 2025-01-29 20:26:55
ジャッジサーバーID
（参考情報） 		judge5 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 1 WA * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
constexpr int INF = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr double EPS = 1e-8;
constexpr int MOD = 1000000007;
// constexpr int MOD = 998244353;
constexpr int DY4[]{1, 0, -1, 0}, DX4[]{0, -1, 0, 1};
constexpr int DY8[]{1, 1, 0, -1, -1, -1, 0, 1};
constexpr int DX8[]{0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U>
inline bool chmax(T& a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U>
inline bool chmin(T& a, U b) { return a > b ? (a = b, true) : false; }
struct IOSetup {
  IOSetup() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << fixed << setprecision(20);
  }
} iosetup;

template <typename CommutativeSemigroup, typename E, typename F, typename G>
std::vector<CommutativeSemigroup> rerooting_dp(
    const std::vector<std::vector<int>>& graph,
    const std::vector<CommutativeSemigroup>& def,
    const E merge, const F f, const G g) {
  const int n = graph.size();
  if (n == 0) return {};
  if (n == 1) return {g(def[0], 0)};
  std::vector<std::vector<CommutativeSemigroup>> children(n);
  const std::function<CommutativeSemigroup(const int, const int)> dfs1 =
      [&graph, &def, merge, f, g, &children, &dfs1](
          const int par, const int ver) -> CommutativeSemigroup {
        children[ver].reserve(graph[ver].size());
        CommutativeSemigroup dp = def[ver];
        for (const int e : graph[ver]) {
          if (e == par) {
            children[ver].emplace_back();
          } else {
            children[ver].emplace_back(f(dfs1(ver, e), ver, e));
            dp = merge(dp, children[ver].back());
          }
        }
        return g(dp, ver);
      };
  dfs1(-1, 0);
  std::vector<CommutativeSemigroup> dp = def;
  const std::function<void(const int, const int,
                           const CommutativeSemigroup&)> dfs2 =
      [&graph, &def, merge, f, g, &children, &dp, &dfs2](
          const int par, const int ver, const CommutativeSemigroup& m) -> void {
        const int c = graph[ver].size();
        for (int i = 0; i < c; ++i) {
          if (graph[ver][i] == par) {
            children[ver][i] = f(m, ver, graph[ver][i]);
            break;
          }
        }
        std::vector<CommutativeSemigroup> left{def[ver]}, right;
        left.reserve(c);
        for (int i = 0; i < c - 1; ++i) {
          left.emplace_back(merge(left[i], children[ver][i]));
        }
        dp[ver] = g(merge(left.back(), children[ver].back()), ver);
        if (c >= 2) {
          right.reserve(c - 1);
          right.emplace_back(children[ver].back());
          for (int i = c - 2; i > 0; --i) {
            right.emplace_back(merge(children[ver][i], right[c - 2 - i]));
          }
          std::reverse(right.begin(), right.end());
        }
        for (int i = 0; i < c; ++i) {
          if (graph[ver][i] != par) {
            dfs2(ver, graph[ver][i],
                 g(i + 1 == c ? left[i] : merge(left[i], right[i]), ver));
          }
        }
      };
  dfs2(-1, 0, CommutativeSemigroup());
  return dp;
}

int main() {
  int n; cin >> n;
  vector<vector<int>> graph(n);
  REP(_, n - 1) {
    int u, v; cin >> u >> v; --u; --v;
    graph[u].emplace_back(v);
    graph[v].emplace_back(u);
  }
  vector<vector<pair<int, int>>> children(n), diameter(n);
  auto f = [&](auto&& f, int par, int ver) -> void {
    for (int e : graph[ver]) {
      if (e == par) continue;
      f(f, ver, e);
      if (children[e].empty()) {
        children[ver].emplace_back(1, e);
        diameter[ver].emplace_back(0, e);
      } else {
        children[ver].emplace_back(children[e].front().first + 1, e);
        if (children[e].size() == 1) {
          diameter[ver].emplace_back(max(children[e].front().first, diameter[e].front().first), e);
        } else if (children[e].size() >= 2) {
          diameter[ver].emplace_back(max(children[e][0].first + children[e][1].first, diameter[e].front().first), e);
        }
      }
    }
    sort(ALL(children[ver]), greater<pair<int, int>>());
    sort(ALL(diameter[ver]), greater<pair<int, int>>());
  };
  f(f, -1, 0);
  // cout << "[children]\n";
  // REP(i, n) {
  //   cout << i << ':';
  //   for (const auto [v, e] : children[i]) {
  //     cout << " {" << v << ',' << e << '}';
  //   }
  //   cout << '\n';
  // }
  // cout << "[diameter]\n";
  // REP(i, n) {
  //   cout << i << ':';
  //   for (const auto [v, e] : diameter[i]) {
  //     cout << " {" << v << ',' << e << '}';
  //   }
  //   cout << '\n';
  // }
  auto g = [&](auto&& g, int par, int ver, int dp1, int dp2) -> void {
    if (par != -1) {
      children[ver].emplace_back(dp1, par);
      diameter[ver].emplace_back(dp2, par);
    }
    sort(ALL(children[ver]), greater<pair<int, int>>());
    sort(ALL(diameter[ver]), greater<pair<int, int>>());
    for (int e : graph[ver]) {
      if (e == par) continue;
      int nxt_dp1 = 1;
      if (children[ver].front().second != e) {
        nxt_dp1 = children[ver].front().first + 1;
      } else if (children[ver].size() >= 2) {
        nxt_dp1 = children[ver][1].first + 1;
      }
      int nxt_dp2 = 0;
      if (children[ver].size() == 2) {
        if (children[ver].front().second == e) {
          nxt_dp2 = children[ver][1].first;
        } else {
          nxt_dp2 = children[ver].front().first;
        }
      } else if (children[ver].size() >= 3) {
        if (children[ver].front().second == e) {
          nxt_dp2 = children[ver][1].first + children[ver][2].first;
        } else if (children[ver][1].second == e) {
          nxt_dp2 = children[ver].front().first + children[ver][2].first;
        } else {
          nxt_dp2 = children[ver].front().first + children[ver][1].first;
        }
      }
      int nxt_dp3 = 0;
      if (diameter[ver].front().second != e) {
        nxt_dp3 = diameter[ver].front().first;
      } else if (diameter[ver].size() >= 2) {
        nxt_dp3 = diameter[ver][1].first;
      }
      g(g, ver, e, nxt_dp1, max(nxt_dp2, nxt_dp3));
    }
  };
  g(g, -1, 0, 0, 0);
  // cout << "[children]\n";
  // REP(i, n) {
  //   cout << i << ':';
  //   for (const auto [v, e] : children[i]) {
  //     cout << " {" << v << ',' << e << '}';
  //   }
  //   cout << '\n';
  // }
  // cout << "[diameter]\n";
  // REP(i, n) {
  //   cout << i << ':';
  //   for (const auto [v, e] : diameter[i]) {
  //     cout << " {" << v << ',' << e << '}';
  //   }
  //   cout << '\n';
  // }
  int ans = INF;
  REP(i, n) {
    for (int e : graph[i]) {
      int child_diameter = 0;
      if (children[e].front().second != i) {
        child_diameter = children[e].front().first;
      } else if (diameter[e].size() >= 2) {
        child_diameter = children[e][1].first;
      }
      int root_diameter = 0;
      if (children[i].size() == 2) {
        if (children[i].front().second == e) {
          root_diameter = children[i][1].first;
        } else {
          root_diameter = children[i].front().first;
        }
      } else if (children[i].size() >= 3) {
        if (children[i].front().second == e) {
          root_diameter = children[i][1].first + children[i][2].first;
        } else if (children[i][1].second == e) {
          root_diameter = children[i].front().first + children[i][2].first;
        } else {
          root_diameter = children[i].front().first + children[i][1].first;
        }
      }
      // cout << i << ": " << root_diameter << ' ' << child_diameter << '\n';
      chmin(ans, (root_diameter + 1) / 2 + (child_diameter + 1) / 2 + 1);
    }
  }
  cout << ans << '\n';
  return 0;
}
0