結果
問題 | No.1098 LCAs |
ユーザー |
![]() |
提出日時 | 2020-05-22 08:45:38 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 750 bytes |
コンパイル時間 | 1,620 ms |
コンパイル使用メモリ | 174,412 KB |
実行使用メモリ | 18,048 KB |
最終ジャッジ日時 | 2024-11-22 16:19:50 |
合計ジャッジ時間 | 8,702 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 2 |
other | AC * 2 WA * 26 |
ソースコード
#include <bits/stdc++.h>using namespace std;void dfs(vector<pair<long long, long long>> &dp, vector<vector<int>> &c, int v){for (int w : c[v]){dfs(dp, c, w);dp[v].first += dp[w].first + 1;dp[v].second += (dp[w].first + 1) * (dp[w].first + 1);}return;}int main(){int N;cin >> N;vector<int> p(N);for (int i = 1; i < N; i++){cin >> p[i];p[i]--;}vector<vector<int>> c(N);for (int i = 1; i < N; i++){c[p[i]].push_back(i);}vector<pair<long long, long long>> dp(N);dfs(dp, c, 0);vector<long long> ans(N);for (int i = 0; i < N; i++){ans[i] = dp[i].first * dp[i].first - dp[i].second + dp[i].first * 2 + 1;}for (int i = 0; i < N; i++){cout << ans[i] << endl;}}