結果

問題 No.3206 う　し　た　ウ　ニ　木　あ　く　ん　笑
ユーザー hiromi_ayase
提出日時 2025-07-18 22:28:27
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 223 ms / 3,000 ms
コード長 1,973 bytes
コンパイル時間 6,355 ms
コンパイル使用メモリ 334,432 KB
実行使用メモリ 65,800 KB
最終ジャッジ日時 2025-07-18 22:28:38
合計ジャッジ時間 9,132 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#include <atcoder/all>
using namespace std;
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
#define FAST_IO                \
  ios::sync_with_stdio(false); \
  cin.tie(0);
const i64 INF = 1001001001001001001;
using Modint = atcoder::static_modint<998244353>;

vector<int> dp1, dp2;
vector<vector<int>> G;

void dfs(int v, int p) {
  dp1[v] = 0;
  for (int u : G[v]) {
    if (u == p) continue;
    dfs(u, v);
    dp1[v] = max(dp1[v], dp1[u] + 1);
  }
}

void dfs2(int v, int p, int d) {
  dp2[v] = d;

  int s = G[v].size();
  vector<int> lmx(s + 1, 0), rmx(s + 1, 0);

  for (int i = 0; i < s; ++i) {
    int u = G[v][i];
    lmx[i + 1] = max(lmx[i], u == p ? 0 : dp1[u] + 1);
  }
  for (int i = s - 1; i >= 0; --i) {
    int u = G[v][i];
    rmx[i] = max(rmx[i + 1], u == p ? 0 : dp1[u] + 1);
  }

  for (int i = 0; i < s; ++i) {
    int u = G[v][i];
    if (u == p) continue;
    int mx = max(max(lmx[i], rmx[i + 1]), d);
    dfs2(u, v, mx + 1);
  }
}

vector<vector<int>> a;
void dfs3(int v, int p) {
  int s = G[v].size();
  a[v].resize(s);
  for (int i = 0; i < s; ++i) {
    int u = G[v][i];
    if (u == p) {
      a[v][i] = dp2[v];
    } else {
      a[v][i] = dp1[u] + 1;
      dfs3(u, v);
    }
  }
  sort(a[v].begin(), a[v].end(), greater<int>());
}

int main() {
  FAST_IO

  int N;
  cin >> N;
  vector<int> u(N - 1), v(N - 1);
  for (int i = 0; i < N - 1; ++i) {
    cin >> u[i] >> v[i];
    u[i]--;
    v[i]--;
  }
  G.resize(N);
  for (int i = 0; i < N - 1; ++i) {
    G[u[i]].push_back(v[i]);
    G[v[i]].push_back(u[i]);
  }
  dp1.resize(N, 0);
  dp2.resize(N, 0);
  a.resize(N);

  dfs(0, -1);
  dfs2(0, -1, 0);
  dfs3(0, -1);

  int ans = 0;
  for (int i = 0; i < N; ++i) {
    int s = G[i].size();
    int mn = 1e9;
    for (int j = 0; j < s; ++j) {
      mn = min(mn, a[i][j]);
      int cur = mn * (j + 1) + 1;
      ans = max(ans, cur);
    }
  }
  cout << ans << endl;
}
0