結果

問題 No.439 チワワのなる木
ユーザー rapurasurapurasu
提出日時 2016-11-01 12:31:51
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 223 ms / 5,000 ms
コード長 2,163 bytes
コンパイル時間 1,603 ms
コンパイル使用メモリ 164,312 KB
実行使用メモリ 126,592 KB
最終ジャッジ日時 2024-11-25 00:41:38
合計ジャッジ時間 4,584 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 36 ms
99,784 KB
testcase_01 AC 37 ms
99,652 KB
testcase_02 AC 36 ms
99,908 KB
testcase_03 AC 36 ms
99,524 KB
testcase_04 AC 36 ms
99,400 KB
testcase_05 AC 37 ms
99,656 KB
testcase_06 AC 37 ms
98,248 KB
testcase_07 AC 37 ms
99,788 KB
testcase_08 AC 37 ms
98,764 KB
testcase_09 AC 36 ms
98,376 KB
testcase_10 AC 39 ms
98,884 KB
testcase_11 AC 37 ms
98,888 KB
testcase_12 AC 37 ms
99,140 KB
testcase_13 AC 38 ms
98,892 KB
testcase_14 AC 37 ms
98,764 KB
testcase_15 AC 38 ms
99,784 KB
testcase_16 AC 38 ms
100,296 KB
testcase_17 AC 38 ms
99,908 KB
testcase_18 AC 145 ms
107,588 KB
testcase_19 AC 125 ms
106,700 KB
testcase_20 AC 183 ms
110,408 KB
testcase_21 AC 70 ms
102,344 KB
testcase_22 AC 65 ms
102,856 KB
testcase_23 AC 200 ms
111,684 KB
testcase_24 AC 223 ms
121,416 KB
testcase_25 AC 145 ms
112,272 KB
testcase_26 AC 136 ms
111,884 KB
testcase_27 AC 139 ms
126,592 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define MAX_N 1000000
int N;
string S;
int tree_c;
int tree_w;
int total_c[MAX_N];
int total_w[MAX_N];
//xを根つき木にする隣接頂点
vector<int> G[MAX_N];
vector<int> Tree[MAX_N];
vector<int> Tree_c[MAX_N];
vector<int> Tree_w[MAX_N];
bool used[MAX_N];
//有向根つき木の構成(再帰部分)
void rec_make_tree(int x){
     if(used[x]==true)return;
     used[x]=true;
     REP(i,G[x].size()){
        if(used[G[x][i]]==false){
           Tree[x].push_back(G[x][i]);
           Tree_c[x].push_back(0);
           Tree_w[x].push_back(0);
           rec_make_tree(G[x][i]);
        }
     }
}
//有向根つき木の構成
void make_tree(int x){
   REP(i,MAX_N){
       used[i]=false;
   }
   rec_make_tree(x);
}
//入力
void input(){
     cin>>N>>S;
     REP(i,N-1){
         int a, b;
         cin>>a>>b;
         G[a-1].push_back(b-1);
         G[b-1].push_back(a-1);
     }
}
//再帰処理
long long dfs(int x){
     long long ans=0;
     long long tc=0,tw=0;//cの数とwの数
     REP(i,Tree[x].size()){
         int temp=Tree[x][i];
         ans+=dfs(temp);
         Tree_c[x][i]=total_c[temp];
         Tree_w[x][i]=total_w[temp];
         tc+=total_c[temp];
         tw+=total_w[temp];
     }

     if(S[x]=='c'){
        tc++;
     }else{
        tw++;
     }
     total_c[x]=tc;
     total_w[x]=tw;
     //最後に残りの向きの値も入れる
     Tree_c[x].push_back(tree_c-tc);
     Tree_w[x].push_back(tree_w-tw);
     
     if(S[x]=='w'){
        REP(i,Tree_c[x].size()){
            ans+=Tree_c[x][i]*(tree_w-Tree_w[x][i]-1);
        }
     }
     //cout<<x<<" "<<ans<<endl;
     return ans;
}

long long solve(){
   //木の作成
   make_tree(0);
   //木全体のcとwをカウント
   tree_c=0;
   tree_w=0;
   REP(i,S.size()){
       if(S[i]=='c'){
          tree_c++;
       }else{
          tree_w++;
       }
   }
   return dfs(0);
}

int main(){
	input();

	cout<<solve()<<endl;
	return(0);
}
0