結果
問題 | No.439 チワワのなる木 |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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;}