結果

問題 No.439 チワワのなる木
ユーザー anta
提出日時 2016-10-28 22:56:34
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 123 ms / 5,000 ms
コード長 3,311 bytes
コンパイル時間 1,859 ms
コンパイル使用メモリ 178,160 KB
実行使用メモリ 24,244 KB
最終ジャッジ日時 2024-11-24 06:10:22
合計ジャッジ時間 3,700 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }
vector<int> t_parent;
vi t_ord;
void tree_getorder(const vector<vi> &g, int root) {
    int n = g.size();
    t_parent.assign(n, -1);
    t_ord.clear();
    vector<int> stk; stk.push_back(root);
    while(!stk.empty()) {
        int i = stk.back(); stk.pop_back();
        t_ord.push_back(i);
        for(int j = (int)g[i].size() - 1; j >= 0; j --) {
            int c = g[i][j];
            if(t_parent[c] == -1 && c != root)
                stk.push_back(c);
            else
                t_parent[i] = c;
        }
    }
}
template<typename Sum, typename Combine, typename Calc>
void freeTreeDP(const vector<int> &t_ord, const vector<int> &t_parent, vector<Sum> &downsum, vector<Sum> &upsum, Sum identity, Combine combine, Calc 
    calc) {
    int n = (int)t_ord.size();
    vector<int> children(n, 0), childid(n, -1);
    for(int ix = 1; ix < (int)t_ord.size(); ++ ix) {
        int i = t_ord[ix], p = t_parent[i];
        childid[i] = children[p] ++;
    }
    vector<vector<Sum>> prefix(n), suffix(n);
    for(int i = 0; i < n; ++ i) {
        prefix[i].assign(children[i] + 1, identity);
        suffix[i].assign(children[i] + 1, identity);
    }
    downsum.assign(n, identity);
    upsum.assign(n, identity);
    for(int ix = (int)t_ord.size() - 1; ix >= 0; -- ix) {
        int i = t_ord[ix], p = t_parent[i];
        for(int j = 0; j < children[i]; ++ j)
            prefix[i][j + 1] = combine(prefix[i][j], prefix[i][j + 1]);
        for(int j = children[i]; j > 0; -- j)
            suffix[i][j - 1] = combine(suffix[i][j - 1], suffix[i][j]);
        if(p != -1) {
            downsum[i] = calc(p, i, suffix[i][0]);
            prefix[p][childid[i] + 1] = downsum[i];
            suffix[p][childid[i]] = downsum[i];
        }
    }
    downsum[t_ord[0]] = suffix[t_ord[0]][0];
    for(int ix = 1; ix < (int)t_ord.size(); ++ ix) {
        int i = t_ord[ix], p = t_parent[i];
        Sum sum = suffix[p][childid[i] + 1];
        sum = combine(sum, upsum[p]);
        sum = combine(sum, prefix[p][childid[i]]);
        upsum[i] = calc(i, p, sum);
    }
}
int main() {
    int N;
    while(~scanf("%d", &N)) {
        char S[100001];
        scanf("%s", S);
        vector<vector<int> > g(N);
        for(int i = 0; i < N - 1; ++ i) {
            int u, v;
            scanf("%d%d", &u, &v), -- u, -- v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        tree_getorder(g, 0);
        vector<int> downC, upC, downW, upW;
        freeTreeDP(t_ord, t_parent, downC, upC, 0, plus<int>(), [&S](int from, int to, int sum) {
            return sum + (S[to] == 'c');
        });
        freeTreeDP(t_ord, t_parent, downW, upW, 0, plus<int>(), [&S](int from, int to, int sum) {
            return sum + (S[to] == 'w');
        });
        ll ans = 0;
        rep(i, N) if(S[i] == 'w') {
            int sumC = 0, sumW = 0;
            ll sumProd = 0;
            for(int j : g[i]) {
                int c = j != t_parent[i] ? downC[j] : upC[i];
                int w = j != t_parent[i] ? downW[j] : upW[i];
                sumC += c;
                sumW += w;
                sumProd += (ll)c * w;
            }
            ans += (ll)sumC * sumW - sumProd;
        }
        printf("%lld\n", ans);
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0