結果

問題 No.439 チワワのなる木
ユーザー vjudge1
提出日時 2024-12-23 20:30:31
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 86 ms / 5,000 ms
コード長 1,080 bytes
コンパイル時間 3,070 ms
コンパイル使用メモリ 247,660 KB
実行使用メモリ 17,664 KB
最終ジャッジ日時 2024-12-23 20:30:37
合計ジャッジ時間 5,065 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define int long long
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
template<typename T>istream&operator>>(istream&I,vector<T>&v){for(auto&i:v)I>>i;return I;}
template<typename T>ostream&operator<<(ostream&O,vector<T>&v){for(auto&i:v)O<<i<<' ';return O;}
namespace AC{
int wcnt[100010],ccnt[100010],f[100010];
vector<int>g[100010];
string s;
void dfs(int u,int fa){
	f[u]=fa;
	for(auto v:g[u]){
		if(v==fa)continue;
		dfs(v,u);
		wcnt[u]+=wcnt[v];
		ccnt[u]+=ccnt[v];
	}
	if(s[u-1]=='w')wcnt[u]++;
	else ccnt[u]++;
}
void solve(){
	int n;
	cin>>n>>s;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1,0);
	int totw=wcnt[1],totc=ccnt[1],tot=0;
	for(int i=1;i<=n;i++)if(s[i-1]=='w'){
		int w=0,c=0,tmp=0;
		for(auto v:g[i])if(v!=f[i])w+=wcnt[v],c+=ccnt[v],tmp+=wcnt[v]*ccnt[v];
		w+=totw-wcnt[i],c+=totc-ccnt[i],tmp+=(totw-wcnt[i])*(totc-ccnt[i]);
		int ans=w*c-tmp;
		tot+=ans;
	}
	cout<<tot<<'\n';
}
}
signed main(){
	int t=1;
	//cin>>t;
	while(t--)AC::solve();
}
0