結果
問題 | No.439 チワワのなる木 |
ユーザー |
![]() |
提出日時 | 2016-10-28 23:00:18 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 111 ms / 5,000 ms |
コード長 | 1,218 bytes |
コンパイル時間 | 2,034 ms |
コンパイル使用メモリ | 160,876 KB |
実行使用メモリ | 18,304 KB |
最終ジャッジ日時 | 2024-11-24 06:13:17 |
合計ジャッジ時間 | 3,898 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define int long long typedef vector<int>vint; typedef pair<int,int>pint; typedef vector<pint>vpint; #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define all(v) (v).begin(),(v).end() #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) #define pb push_back #define fi first #define se second template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;} template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;} int N; string S; vint G[100000]; int ans; int allC,allW; int C[100000],W[100000]; void dfs(int v,int p){ if(S[v]=='c')C[v]++; else W[v]++; for(auto u:G[v]){ if(u==p)continue; dfs(u,v); C[v]+=C[u]; W[v]+=W[u]; } if(S[v]=='c')return; for(auto u:G[v]){ if(u==p)continue; ans+=C[u]*(allW-W[u]-1); } ans+=(allC-C[v])*(W[v]-1); } signed main(){ cin>>N>>S; rep(i,N-1){ int a,b; cin>>a>>b; a--;b--; G[a].pb(b);G[b].pb(a); } rep(i,N){ if(S[i]=='c')allC++; else allW++; } dfs(0,-1); cout<<ans<<endl; return 0; }