結果
問題 | No.439 チワワのなる木 |
ユーザー |
![]() |
提出日時 | 2016-10-28 23:42:34 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 108 ms / 5,000 ms |
コード長 | 2,006 bytes |
コンパイル時間 | 1,875 ms |
コンパイル使用メモリ | 161,140 KB |
実行使用メモリ | 18,816 KB |
最終ジャッジ日時 | 2024-11-24 06:34:08 |
合計ジャッジ時間 | 3,333 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:109:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 109 | scanf("%d %s",&n,s); | ~~~~~^~~~~~~~~~~~~~ main.cpp:112:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 112 | scanf("%d %d",&a,&b); | ~~~~~^~~~~~~~~~~~~~~
ソースコード
#include<bits/stdc++.h>using namespace std;#define MAX_N 100005typedef long long ll;int n;char s[MAX_N];vector<int> G[MAX_N];int par[MAX_N];ll wc[MAX_N];ll cc[MAX_N];void dfs(int pos,int prev){if(s[pos]=='w')wc[pos]++;if(s[pos]=='c')cc[pos]++;par[pos]=prev;for(int i=0;i<(int)G[pos].size();i++){int to=G[pos][i];if(to==prev)continue;dfs(to,pos);wc[pos]+=wc[to];cc[pos]+=cc[to];}}ll mem[MAX_N];ll ww(int pos){if(mem[pos]!=-1)return mem[pos];ll res=0;if(s[pos]=='w')res+= wc[pos]-1;for(int i=0;i<(int)G[pos].size();i++){int to=G[pos][i];if(to==par[pos])continue;res+=ww(to);}return mem[pos]=res;}ll Mem[MAX_N];ll cw(int pos){if(Mem[pos]!=-1)return Mem[pos];ll res=0;if(s[pos]=='w')res+=cc[pos];for(int i=0;i<(int)G[pos].size();i++){int to=G[pos][i];if(to==par[pos])continue;res+=cw(to);}return Mem[pos]=res;}ll cww(int pos){ll res=0;if(s[pos]=='c'){for(int i=0;i<(int)G[pos].size();i++){int to=G[pos][i];if(to==par[pos])continue;res+=ww(G[pos][i]);}}else if(s[pos]=='w'){ll C=0,W=0;for(int i=0;i<(int)G[pos].size();i++){int to=G[pos][i];if(to==par[pos])continue;res+= C*wc[to];res+= W*cc[to];W+=wc[to];C+=cc[to];res+=cw(to);}}ll C=0,WW=0;ll CW=0,W=0;for(int i=0;i<(int)G[pos].size();i++){int to=G[pos][i];if(to==par[pos])continue;res+= cc[to]*WW;res+= ww(to)*C;res+= cw(to)*W;res+= wc[to]*CW;C+=cc[to];W+=wc[to];CW+=cw(to);WW+=ww(to);}return res;}int main(){for(int i=0;i<MAX_N;i++){mem[i]=-1;Mem[i]=-1;}scanf("%d %s",&n,s);for(int i=0;i<n-1;i++){int a,b;scanf("%d %d",&a,&b);a--,b--;G[a].push_back(b);G[b].push_back(a);}dfs(0,-1);ll ans=0;for(int i=0;i<n;i++){ans+= cww(i);}printf("%lld\n",ans);return 0;}