結果

問題 No.439 チワワのなる木
ユーザー rapurasurapurasu
提出日時 2016-11-01 12:31:51
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 216 ms / 5,000 ms
コード長 2,163 bytes
コンパイル時間 1,220 ms
コンパイル使用メモリ 162,816 KB
実行使用メモリ 124,032 KB
最終ジャッジ日時 2024-05-03 20:37:17
合計ジャッジ時間 4,339 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
98,176 KB
testcase_01 AC 38 ms
98,176 KB
testcase_02 AC 37 ms
98,048 KB
testcase_03 AC 35 ms
98,176 KB
testcase_04 AC 35 ms
98,176 KB
testcase_05 AC 36 ms
98,176 KB
testcase_06 AC 36 ms
98,176 KB
testcase_07 AC 38 ms
98,176 KB
testcase_08 AC 39 ms
98,176 KB
testcase_09 AC 38 ms
98,176 KB
testcase_10 AC 37 ms
98,176 KB
testcase_11 AC 36 ms
98,176 KB
testcase_12 AC 35 ms
97,920 KB
testcase_13 AC 36 ms
98,304 KB
testcase_14 AC 36 ms
98,304 KB
testcase_15 AC 37 ms
98,304 KB
testcase_16 AC 37 ms
98,432 KB
testcase_17 AC 37 ms
98,432 KB
testcase_18 AC 148 ms
107,008 KB
testcase_19 AC 126 ms
106,496 KB
testcase_20 AC 181 ms
109,696 KB
testcase_21 AC 66 ms
101,760 KB
testcase_22 AC 64 ms
101,376 KB
testcase_23 AC 203 ms
111,744 KB
testcase_24 AC 216 ms
121,600 KB
testcase_25 AC 142 ms
110,080 KB
testcase_26 AC 135 ms
109,976 KB
testcase_27 AC 144 ms
124,032 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