結果

問題 No.439 チワワのなる木
ユーザー antaanta
提出日時 2016-10-28 22:56:34
言語 C++14
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 2 ms
5,248 KB
testcase_13 AC 2 ms
5,248 KB
testcase_14 AC 2 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 81 ms
17,536 KB
testcase_19 AC 69 ms
17,020 KB
testcase_20 AC 112 ms
21,728 KB
testcase_21 AC 26 ms
9,312 KB
testcase_22 AC 25 ms
8,284 KB
testcase_23 AC 123 ms
22,952 KB
testcase_24 AC 123 ms
22,928 KB
testcase_25 AC 97 ms
24,132 KB
testcase_26 AC 93 ms
24,244 KB
testcase_27 AC 74 ms
22,936 KB
権限があれば一括ダウンロードができます

ソースコード

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;
}
0