結果

問題 No.439 チワワのなる木
ユーザー rapurasu
提出日時 2016-11-01 12:31:51
言語 C++11（廃止可能性あり）
(gcc 13.3.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

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