結果

問題 No.439 チワワのなる木
ユーザー 🍡yurahuna
提出日時 2016-04-29 01:19:44
言語 C++14
(gcc 8.3.0)
結果
AC  
実行時間 77 ms
コード長 2,661 Byte
コンパイル時間 1,363 ms
使用メモリ 16,340 KB
最終ジャッジ日時 2019-10-06 19:43:25

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
in01.txt AC 5 ms
3,112 KB
in02.txt AC 5 ms
3,108 KB
in03.txt AC 5 ms
3,108 KB
in04.txt AC 4 ms
3,112 KB
in05.txt AC 5 ms
3,108 KB
in06.txt AC 5 ms
3,108 KB
in07.txt AC 4 ms
3,108 KB
in08.txt AC 4 ms
3,108 KB
r01.txt AC 4 ms
3,124 KB
r02.txt AC 4 ms
3,120 KB
r03.txt AC 4 ms
3,128 KB
r04.txt AC 5 ms
3,108 KB
r05.txt AC 5 ms
3,120 KB
r06.txt AC 5 ms
3,148 KB
r07.txt AC 5 ms
3,148 KB
r08.txt AC 5 ms
3,204 KB
r09.txt AC 5 ms
3,240 KB
r10.txt AC 5 ms
3,208 KB
r11.txt AC 45 ms
7,368 KB
r12.txt AC 39 ms
7,368 KB
r13.txt AC 62 ms
8,688 KB
r14.txt AC 17 ms
4,992 KB
r15.txt AC 17 ms
4,464 KB
z01.txt AC 68 ms
9,744 KB
z02.txt AC 77 ms
15,288 KB
z03.txt AC 47 ms
9,268 KB
z04.txt AC 45 ms
9,336 KB
z05.txt AC 46 ms
16,340 KB
テストケース一括ダウンロード

ソースコード

diff #
#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()

typedef long long ll;
typedef pair<int, int> P;

// O(N)解
// 2回DFSする

struct Chiwawa {
    int w, ww;
    Chiwawa() { w = 0, ww = 0; }
};

const int MAX_N = 100000;

int N;
string s;
vector<vector<int>> G;
Chiwawa cww[MAX_N];    // 各頂点を根とした部分木に含まれる(w, ww)の個数 (一番上の親は0)

// 配列cwwを用意するためのdfs
Chiwawa dfs(int now, int pre) {
    Chiwawa ret;

    for (auto nxt : G[now]) {
        if (nxt == pre) continue;
        auto child = dfs(nxt, now);
        ret.w += child.w;
        ret.ww += child.ww;
    }

    if (s[now] == 'w') {
        // 自分がwなら、子のwの数だけwwが増える
        ret.ww += ret.w;
        // wは1増える
        ++ret.w;
    }

    cww[now] = ret;
    return ret;
}

int ans; // 答えの記録用

// 答えを求めるdfs
// p: vの部分木に含まれない(w, ww)の個数
void dfs2(int v, int pre, Chiwawa p) {
    // この頂点がcなら、つなげられるwwの個数を答えに加える
    if (s[v] == 'c') {
        ans += p.ww;    // pのwwとつなげたとき
        for (auto ch : G[v]) {
            if (ch == pre) continue;
            ans += cww[ch].ww;  // chの部分木のwwとつなげたとき
        }
    }


    for (auto ch : G[v]) {
        if (ch == pre) continue;
        // 次の子に渡すためにpを更新する
        auto tmp = p;
        // vの部分木のうち、chの部分木の分を除く
        tmp.w += cww[v].w, tmp.ww += cww[v].ww;
        tmp.w -= cww[ch].w, tmp.ww -= cww[ch].ww;
        if (s[v] == 'w') {
            // vが 'w' の場合は、 vの 'w' を使っている分のwwの個数が変化する
            // v の 'w' と chの部分木の 'w' を使っている ww は減る
            tmp.ww -= cww[ch].w;
            // v の 'w' と p の 'w' を使っている ww が増える
            tmp.ww += p.w;
        }
        // 子に移動
        dfs2(ch, v, tmp);
    }


}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    cin >> N;
    cin >> s;

    G.resize(N);
    rep(i, N - 1) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        G[a].emplace_back(b);
        G[b].emplace_back(a);
    }

    // 準備
    dfs(0, -1);

    // 本番
    dfs2(0, -1, Chiwawa());

    cout << ans << endl;

}
0