結果
問題 | 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;}