結果

問題 No.1098 LCAs
コンテスト
ユーザー snrnsidy
提出日時 2021-05-13 04:00:53
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 181 ms / 2,000 ms
コード長 826 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,867 ms
コンパイル使用メモリ 194,676 KB
最終ジャッジ日時 2025-01-21 10:24:41
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

using namespace std;

long long int dp[200005];
vector <int> adj[200005];
long long int cnt[200005];

long long int func(int now, int prev)
{
	cnt[now] = 1;
	for (auto next : adj[now])
	{
		if (next == prev) continue;
		cnt[now] += func(next, now);
	}
	return cnt[now];
}

void solve(int now, int prev)
{
	//cout << now << ' ' << cnt[now] << '\n';
	dp[now] = cnt[now] * cnt[now];
	for (auto next : adj[now])
	{
		if (next == prev) continue;
		solve(next, now);
		dp[now] -= (cnt[next] * cnt[next]);
	}
}

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int n, a, b;

	cin >> n;

	for (int i = 0; i < n - 1; i++)
	{
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	
	func(1, 0);
	solve(1, 0);

	for (int i = 1; i <= n; i++)
	{
		cout << dp[i] << '\n';
	}

	return 0;
}
0