結果

問題 No.439 チワワのなる木
ユーザー snrnsidy
提出日時 2025-09-18 00:13:59
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 105 ms / 5,000 ms
コード長 1,425 bytes
コンパイル時間 2,123 ms
コンパイル使用メモリ 197,812 KB
実行使用メモリ 23,900 KB
最終ジャッジ日時 2025-09-18 00:14:04
合計ジャッジ時間 4,846 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

vector <int> adj[100005];
vector <int> edge[100005];
long long int dp[100005][2];
int n,a,b;
string s;
long long int res = 0;

void maketree(int now,int prev)
{
    for(auto next : edge[now])
    {
        if(next==prev) continue;
        adj[now].push_back(next);
        maketree(next,now);
    }
}

void dfs(int now)
{
    if(s[now]=='c') dp[now][0] += 1;
    else dp[now][1] += 1;

    for(auto next : adj[now])
    {
        dfs(next);
        dp[now][0] += dp[next][0];
        dp[now][1] += dp[next][1];
    }
    return;
}

void solve(int now,long long int C,long long int W)
{
    if(s[now]=='w')
    {
        long long int sumW = W;
        for(auto next : adj[now])
        {
            sumW += dp[next][1];
        }
        res += (C*(sumW - W));
        for(auto next : adj[now])
        {
            res += (dp[next][0]*(sumW - dp[next][1]));
        }
    }
    for(auto next : adj[now])
    {
        long long int c = dp[now][0];
        long long int w = dp[now][1];
        solve(next,C+c-dp[next][0],W+w-dp[next][1]);
    }
}
int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);

    cin >> n;
    cin >> s;
    for(int i=1;i<n;i++)
    {
        cin >> a >> b;
        a-=1;
        b-=1;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }

    maketree(0,-1);
    dfs(0);
    solve(0,0,0);

    cout << res << '\n';

	return 0;
}
0