結果

問題 No.439 チワワのなる木
ユーザー kmjp
提出日時 2016-10-28 23:46:57
言語 C++11
(gcc 4.8.5)
結果
AC  
実行時間 69 ms
コード長 1,264 Byte
コンパイル時間 1,566 ms
使用メモリ 12,540 KB
最終ジャッジ日時 2019-10-11 11:47:39

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
in01.txt AC 7 ms
6,876 KB
in02.txt AC 6 ms
6,876 KB
in03.txt AC 6 ms
6,872 KB
in04.txt AC 6 ms
6,876 KB
in05.txt AC 6 ms
6,876 KB
in06.txt AC 7 ms
6,872 KB
in07.txt AC 7 ms
6,872 KB
in08.txt AC 6 ms
6,872 KB
r01.txt AC 7 ms
6,872 KB
r02.txt AC 6 ms
6,876 KB
r03.txt AC 6 ms
6,876 KB
r04.txt AC 6 ms
8,924 KB
r05.txt AC 5 ms
6,872 KB
r06.txt AC 5 ms
6,872 KB
r07.txt AC 6 ms
6,876 KB
r08.txt AC 5 ms
6,872 KB
r09.txt AC 6 ms
6,872 KB
r10.txt AC 6 ms
8,920 KB
r11.txt AC 47 ms
6,876 KB
r12.txt AC 37 ms
6,872 KB
r13.txt AC 63 ms
7,640 KB
r14.txt AC 17 ms
6,872 KB
r15.txt AC 16 ms
6,872 KB
z01.txt AC 63 ms
8,308 KB
z02.txt AC 69 ms
11,748 KB
z03.txt AC 40 ms
8,000 KB
z04.txt AC 44 ms
8,164 KB
z05.txt AC 36 ms
12,540 KB
テストケース一括ダウンロード

ソースコード

diff #
#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
int TC,TW;
string S;
int CC[101010],CW[101010];
vector<int> E[101010];
ll ret;

void dfs(int cur,int pre) {
	if(S[cur]=='c') CC[cur]=1;
	if(S[cur]=='w') CW[cur]=1;
	
	FORR(e,E[cur]) if(e!=pre) {
		dfs(e,cur);
		CC[cur]+=CC[e];
		CW[cur]+=CW[e];
		if(S[cur]=='w') ret += 1LL*CC[e]*(TW-1-CW[e]);
	}
	
	if(pre!=-1 && S[cur]=='w') ret += 1LL*(TC-CC[cur])*(CW[cur]-1);
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	FORR(c,S) if(c=='c') TC++;
	FORR(c,S) if(c=='w') TW++;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	dfs(0,-1);
	cout<<ret<<endl;
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n';
	FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	solve(); return 0;
}
0