結果

問題 No.3206 う　し　た　ウ　ニ　木　あ　く　ん　笑
ユーザー noshinn
提出日時 2025-06-12 11:30:06
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 128 ms / 3,000 ms
コード長 2,444 bytes
コンパイル時間 2,185 ms
コンパイル使用メモリ 209,460 KB
実行使用メモリ 35,324 KB
最終ジャッジ日時 2025-07-16 01:14:37
合計ジャッジ時間 4,773 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void search(vector<vector<int>> &tree, vector<pair<int, int>> &dist, int u,
            int parent, vector<int> &par) {
  par[u] = parent;
  int one = 0, two = 0;
  if (tree[u].size() == 1 and tree[u][0] == parent) {
    dist[u] = {0, 0};
    return;
  }
  for (auto p : tree[u]) {
    if (p == parent)
      continue;
    search(tree, dist, p, u, par);
    if (two < dist[p].first + 1) {
      two = dist[p].first + 1;
      if (two > one)
        swap(one, two);
    }
  }
  dist[u] = {one, two};
}

void solve() {
  // 各頂点から一番遠い点を保持していればよい。被った時のために二番目まで保持する
  int n;
  cin >> n;
  vector<vector<int>> tree(n + 1);
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    tree[u].push_back(v);
    tree[v].push_back(u);
  }
  // 一旦1を頂点とする
  vector<int> par(n + 1, -1);
  vector<pair<int, int>> dist(n + 1, {-1, -1});
  search(tree, dist, 1, -1, par);

  int ans = 0;
  queue<int> que;
  que.push(1);
  while (!que.empty()) {
    int top = que.front();
    que.pop();
    vector<int> roads;
    // それぞれの子どもについて考えてからpush
    for (auto p : tree[top]) {
      if (p == par[top])
        continue;
      que.push(p);
      roads.push_back(dist[p].first);
    }
    if (par[top] != -1) {
      // 親が存在するとき、
      if (dist[par[top]].first == dist[top].first + 1) {
        // 親からの最長経路が自分を通るとき
        roads.push_back(dist[par[top]].second);
        if (dist[top].second < dist[par[top]].second + 1)
          dist[top].second = dist[par[top]].second + 1;
      } else {
        // 親からの最長経路が自分を通らないとき
        roads.push_back(dist[par[top]].first);
        if (dist[top].second < dist[par[top]].first + 1)
          dist[top].second = dist[par[top]].first + 1;
      }

      if (dist[top].second > dist[top].first)
        swap(dist[top].first, dist[top].second);
    }
    // ansを更新
    sort(roads.begin(), roads.end());
    reverse(roads.begin(), roads.end());
    for (int i = 0; i < (int)roads.size(); i++) {
      ans = max(ans, 1 + (i + 1) * (roads[i] + 1));
    }
  }
  cout << ans << endl;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cout << fixed << setprecision(20);
  int CNT = 1;
  for (int i = 0; i < CNT; i++)
    solve();
}
0