結果
問題 | No.439 チワワのなる木 |
ユーザー |
![]() |
提出日時 | 2016-10-28 23:01:39 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 124 ms / 5,000 ms |
コード長 | 1,720 bytes |
コンパイル時間 | 1,576 ms |
コンパイル使用メモリ | 175,832 KB |
実行使用メモリ | 43,904 KB |
最終ジャッジ日時 | 2024-11-24 06:13:32 |
合計ジャッジ時間 | 3,255 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 |
ソースコード
#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; }