結果
問題 | No.2638 Initial fare |
ユーザー | Yugimn |
提出日時 | 2024-02-24 22:00:57 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 279 ms / 2,000 ms |
コード長 | 772 bytes |
コンパイル時間 | 3,243 ms |
コンパイル使用メモリ | 255,212 KB |
実行使用メモリ | 57,500 KB |
最終ジャッジ日時 | 2024-09-29 10:17:25 |
合計ジャッジ時間 | 8,453 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
//mosyasu #include<bits/stdc++.h> using namespace std; int main(){ int n; cin >> n; vector ikeru(n, vector<int>(0)); for (int i=0; i<n-1; i++){ int u, v; cin >> u >> v; u--; v--; ikeru[u].push_back(v); ikeru[v].push_back(u); } long long ans = 0; vector dp(n, vector<long long>(4)); vector<int> mx(n, 0); auto dfs = [&](auto self, int i, int p) -> void { dp[i][0] = 1; mx[i] = 1; for (int j: ikeru[i]){ if (j == p) continue; self(self, j, i); for (int x=0; x<mx[i]; x++){ for (int y=0; y<mx[j]; y++){ if (x+y+1 > 3) break; ans += dp[i][x] * dp[j][y]; } } for (int x=0; x<min(3,mx[j]); x++){ dp[i][x+1] += dp[j][x]; } mx[i] = min(4, max(mx[i], mx[j]+1)); } }; dfs(dfs, 0, -1); cout << ans << '\n'; }