結果
問題 |
No.3206 う し た ウ ニ 木 あ く ん 笑
|
ユーザー |
|
提出日時 | 2025-07-21 03:01:25 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 225 ms / 3,000 ms |
コード長 | 2,957 bytes |
コンパイル時間 | 2,387 ms |
コンパイル使用メモリ | 206,844 KB |
実行使用メモリ | 88,388 KB |
最終ジャッジ日時 | 2025-07-21 03:01:33 |
合計ジャッジ時間 | 6,098 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h> using namespace std; //頂点vの子供c1,c2...に対して //givep(v,merge(receive(c1),receive(c2),...))を計算する struct ReRooting{ using T = int; const T identity = 0; //mergeの演算に対する単位元 int n; vector<vector<int>> G; vector<vector<T>> dp; vector<T> ans; //vのi番目の辺の子からRを受け取ったときの処理 T receive(int v,int i,T &R){ return T(R + 1); } //全体の累積lに子receiveの値をmerge //mergeの演算はモノイドでなくてはならない T merge(T l,T r){ return max(l, r); } //親に渡すときの処理 T givep(int v, T cum){ return cum; } ReRooting() {} ReRooting(int N):n(N){ G.resize(N); dp.resize(N); ans.resize(N,identity); } void add_edge(int a, int b) { G[a].emplace_back(b); G[b].emplace_back(a); } void read(){ int a, b; for(int i = 1; i < n; i++){ cin >> a >> b; a--, b--; G[a].emplace_back(b); G[b].emplace_back(a); } } void build() { dfs(0); // 普通に木DP dfs2(0, identity); // 残りの部分木に対応するDPを計算 } T dfs(int v, int p = -1) { T res = identity; int deg = G[v].size(); dp[v] = vector<T>(deg, identity); for (int i = 0; i < deg; i++) { int u = G[v][i]; if (u == p) continue; dp[v][i] = dfs(u, v); res = merge(res, receive(v, i, dp[v][i]) ); } return givep(v, res); } void dfs2(int v, const T& dp_p, int p = -1) { int deg = G[v].size(); for (int i = 0; i < deg; i++) { // 前のdfsで計算した有向辺に対応する部分木のDPを保存 if (G[v][i] == p){dp[v][i] = dp_p; break;} } vector<int> tmp(deg); vector<T> dp_l(deg + 1, identity), dp_r(deg + 1, identity); // 累積merge for (int i = 0; i < deg; i++) { dp_l[i + 1] = merge(dp_l[i], receive(v, i,dp[v][i])); tmp[i] = receive(v, i, dp[v][i]); } for (int i = deg - 1; i >= 0; i--) { dp_r[i] = merge(dp_r[i + 1], receive(v, i,dp[v][i])); } sort(tmp.begin(), tmp.end()); for(int i = 0; i < deg; i++){ ans[v] = max(ans[v], (deg - i) * tmp[i]); } for (int i = 0; i < deg; i++) { // 一つ隣の頂点に対しても同様に計算 int u = G[v][i]; if (u == p) continue; dfs2(u, givep(v, merge(dp_l[i], dp_r[i + 1])),v); } } }; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; ReRooting g(n); g.read(); g.build(); int ans = 0; for(int v = 0; v < n; v++){ ans = max(ans, g.ans[v]); } cout << ans + 1 << '\n'; }