結果
問題 | No.439 チワワのなる木 |
ユーザー | dohatsutsu |
提出日時 | 2016-10-28 23:42:34 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 65 ms / 5,000 ms |
コード長 | 2,006 bytes |
コンパイル時間 | 1,446 ms |
コンパイル使用メモリ | 146,664 KB |
実行使用メモリ | 18,948 KB |
最終ジャッジ日時 | 2023-08-15 21:44:58 |
合計ジャッジ時間 | 3,365 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
8,884 KB |
testcase_01 | AC | 3 ms
8,868 KB |
testcase_02 | AC | 4 ms
8,868 KB |
testcase_03 | AC | 4 ms
8,924 KB |
testcase_04 | AC | 4 ms
8,888 KB |
testcase_05 | AC | 3 ms
8,920 KB |
testcase_06 | AC | 4 ms
8,868 KB |
testcase_07 | AC | 4 ms
8,932 KB |
testcase_08 | AC | 4 ms
9,036 KB |
testcase_09 | AC | 4 ms
8,856 KB |
testcase_10 | AC | 3 ms
8,876 KB |
testcase_11 | AC | 3 ms
8,860 KB |
testcase_12 | AC | 3 ms
8,936 KB |
testcase_13 | AC | 3 ms
8,964 KB |
testcase_14 | AC | 3 ms
9,008 KB |
testcase_15 | AC | 4 ms
8,992 KB |
testcase_16 | AC | 4 ms
9,148 KB |
testcase_17 | AC | 4 ms
9,004 KB |
testcase_18 | AC | 41 ms
11,768 KB |
testcase_19 | AC | 34 ms
11,680 KB |
testcase_20 | AC | 58 ms
12,456 KB |
testcase_21 | AC | 16 ms
10,204 KB |
testcase_22 | AC | 16 ms
9,960 KB |
testcase_23 | AC | 63 ms
13,148 KB |
testcase_24 | AC | 65 ms
17,752 KB |
testcase_25 | AC | 40 ms
12,552 KB |
testcase_26 | AC | 39 ms
12,780 KB |
testcase_27 | AC | 37 ms
18,948 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; #define MAX_N 100005 typedef 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; }