結果
問題 | No.439 チワワのなる木 |
ユーザー | btk |
提出日時 | 2016-10-28 23:01:39 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 104 ms / 5,000 ms |
コード長 | 1,720 bytes |
コンパイル時間 | 1,561 ms |
コンパイル使用メモリ | 172,728 KB |
実行使用メモリ | 42,312 KB |
最終ジャッジ日時 | 2023-08-15 21:28:51 |
合計ジャッジ時間 | 3,051 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 1 ms
4,376 KB |
testcase_04 | AC | 1 ms
4,376 KB |
testcase_05 | AC | 1 ms
4,376 KB |
testcase_06 | AC | 2 ms
4,376 KB |
testcase_07 | AC | 1 ms
4,376 KB |
testcase_08 | AC | 1 ms
4,380 KB |
testcase_09 | AC | 1 ms
4,380 KB |
testcase_10 | AC | 1 ms
4,376 KB |
testcase_11 | AC | 1 ms
4,376 KB |
testcase_12 | AC | 1 ms
4,380 KB |
testcase_13 | AC | 1 ms
4,376 KB |
testcase_14 | AC | 2 ms
4,376 KB |
testcase_15 | AC | 2 ms
4,376 KB |
testcase_16 | AC | 2 ms
4,376 KB |
testcase_17 | AC | 2 ms
4,380 KB |
testcase_18 | AC | 61 ms
17,096 KB |
testcase_19 | AC | 46 ms
15,388 KB |
testcase_20 | AC | 79 ms
21,212 KB |
testcase_21 | AC | 16 ms
8,336 KB |
testcase_22 | AC | 18 ms
8,012 KB |
testcase_23 | AC | 91 ms
24,104 KB |
testcase_24 | AC | 104 ms
38,360 KB |
testcase_25 | AC | 40 ms
19,828 KB |
testcase_26 | AC | 38 ms
19,856 KB |
testcase_27 | AC | 62 ms
42,312 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star; typedef long long LL; template<typename T> istream& operator>>(istream &is,vector<T> &v){ for(auto &it:v)is>>it; return is; } template<typename T>void chmin(T& a, T& b){a=min(a,b);} template<typename T>void chmax(T& a, T& b){a=max(a,b);} int N; string S; typedef vector<LL> V; typedef vector<V> Graph; LL all_c=0,all_w=0; typedef tuple<LL,LL> P; P make_tree(int v,int p,Graph& g,Graph &tree,Graph& c_num,Graph& w_num){ // cout<<v<<p<<endl; LL c=0,w=0; for(auto &u:g[v]) if(u!=p){ tree[v].push_back(u); //cout<<v<<u<<p<<endl; LL cc,ww; tie(cc,ww)=make_tree(u,v,g,tree,c_num,w_num); c_num[v].push_back(cc); w_num[v].push_back(ww); c+=cc; w+=ww; } if(S[v]=='c')c++; else w++; return P(c,w); } LL dfs(int v,Graph &tree,Graph &c_num,Graph &w_num){ //cout<<v<<endl; LL res=0; LL now_w=1,now_c=0; for(int i=0;i<(int)tree[v].size();i++){ //cout<<v<<tree[v][i]<<endl; res+=dfs(tree[v][i],tree,c_num,w_num); if(S[v]=='w'){ res+=w_num[v][i]*(all_c-c_num[v][i]); } now_w+=w_num[v][i]; now_c+=c_num[v][i]; } if(S[v]=='w'){ res+=now_c*(all_w-now_w); } return res; } int main(){ cin>>N>>S; Graph g(N),tree(N),c_num(N),w_num(N); for(int i=1;i<N;i++){ int a,b;cin>>a>>b;a--,b--; g[a].push_back(b); g[b].push_back(a); } tie(all_c,all_w)=make_tree(0,0,g,tree,c_num,w_num); cout<<dfs(0,tree,c_num,w_num)<<endl; return 0; }