結果

問題 No.439 チワワのなる木
ユーザー femto
提出日時 2016-10-28 23:12:32
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 48 ms / 5,000 ms
コード長 924 bytes
コンパイル時間 1,344 ms
コンパイル使用メモリ 171,524 KB
実行使用メモリ 16,772 KB
最終ジャッジ日時 2024-11-24 06:19:56
合計ジャッジ時間 2,579 ms
ジャッジサーバーID
(参考情報)
judge1 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N;
ll ans;
ll C[100000];
ll W[100000];
vector<int> G[100000];
string S;
void dfs1(int n, int p) {
if(S[n] == 'c') C[n]++;
else W[n]++;
for(auto c : G[n]) {
if(c == p) continue;
dfs1(c, n);
C[n] += C[c];
W[n] += W[c];
}
}
void dfs2(int n, int p) {
if(S[n] == 'w') {
ll csum = C[0], wsum = W[0];
for(auto c : G[n]) {
ll cn = 0, wn = 0;
if(c == p) {
cn = csum - C[n];
wn = wsum - W[n];
}
else {
cn = C[c];
wn = W[c];
}
ans += cn * (wsum - 1 - wn);
//ans += wn * (csum - cn);
}
}
for(auto c : G[n]) {
if(c == p) continue;
dfs2(c, n);
}
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
cin >> N;
cin >> S;
for(int i = 0; i < N - 1; i++) {
int a, b;
cin >> a >> b;
a--, b--;
G[a].push_back(b);
G[b].push_back(a);
}
dfs1(0, -1);
dfs2(0, -1);
cout << ans << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0