結果

問題 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();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0