#1032982 (C++23) No.439 チワワのなる木

• 問題: 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

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	2 ms; 5,248 KB
testcase_03	AC	2 ms; 5,248 KB
testcase_04	AC	2 ms; 5,248 KB
testcase_05	AC	2 ms; 5,248 KB
testcase_06	AC	2 ms; 5,248 KB
testcase_07	AC	2 ms; 5,248 KB
testcase_08	AC	2 ms; 5,248 KB
testcase_09	AC	2 ms; 5,248 KB
testcase_10	AC	2 ms; 5,248 KB
testcase_11	AC	2 ms; 5,248 KB
testcase_12	AC	3 ms; 5,248 KB
testcase_13	AC	3 ms; 5,248 KB
testcase_14	AC	3 ms; 5,248 KB
testcase_15	AC	3 ms; 5,248 KB
testcase_16	AC	3 ms; 5,248 KB
testcase_17	AC	3 ms; 5,248 KB
testcase_18	AC	61 ms; 9,472 KB
testcase_19	AC	54 ms; 9,344 KB
testcase_20	AC	80 ms; 11,392 KB
testcase_21	AC	23 ms; 6,016 KB
testcase_22	AC	20 ms; 5,504 KB
testcase_23	AC	86 ms; 12,416 KB
testcase_24	AC	85 ms; 16,768 KB
testcase_25	AC	72 ms; 11,384 KB
testcase_26	AC	68 ms; 12,076 KB
testcase_27	AC	71 ms; 17,664 KB

ソースコード

#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();
}