Submission #36167981

---

Source Code Expand

//#define
#define SHOW(n) cout << #n << " = " << n << endl;
//Visual Studio用
#define _CRT_SECURE_NO_WARNINGS
//include
#include <iostream>
#include <algorithm>
#include <vector>
//名前空間
using namespace std;
//型
using ll = long long;
struct Edge {
	ll to;
	ll weight;
	Edge(ll t, ll w) :to(t), weight(w) {}
};
class Graph {
	vector<vector<Edge>> g;
	int siz;
public:
	Graph(int n) :g(n), siz(n) {};
	vector<Edge>& operator [](int v) {
		return g[v];
	}
	int size()const { return siz; }
	void add(int u, int v, ll w) {
		g[u].push_back({ v,w });
	}
	void add(int u, int v) {
		g[u].push_back(Edge{ v,1 });
	}
	void wadd(int u, int v, ll w) {
		add(u, v, w);
		add(v, u, w);
	}
	void wadd(int u, int v) {
		add(u, v);
		add(v, u);
	}

};
//演算子オーバーロード
template<class T>istream& operator>>(istream& is, vector<T>& v) { for (auto& e : v)is >> e; return is; }

//aclが使えない環境ではコメントアウト
/**/
#include <atcoder/modint.hpp>
using namespace atcoder;
/**/

using mint = modint1000000007;

int main() {
//入出力高速化、cout(cin)とprintf(scanf)を同時に使う場合コメントアウト
	/**/
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	/**/
	
	int n;
	cin >> n;
	vector<char> c(n);
	cin >> c;
	Graph g(n);
	for (int i = 0; i < n - 1; ++i) {
		int a, b;
		cin >> a >> b;
		--a, --b;
		//グラフに双方向に辺を張る
		g.wadd(a, b);
	}
	//dp[pos][st] := 頂点posの部分木とその連結成分について、それぞれの連結成分の状態がすべてstであるときの通り数
	//st 0=aのみ,1=bのみ,2=aとb両方ある
	//res = dp[0][2]
	//mint は modint の略で、自動的にmodを取ってくれる整数型
	vector<vector<mint>> dp(n, vector<mint>(3));

	//頂点vから木dp
	auto dfs = [&](auto&& self, int v, int prev) ->void {
		mint m1 = 1, m2 = 1;
		//頂点vのすべての子頂点sに対して計算
		for (auto [s, w] : g[v]) {
			//逆流防止
			if (s == prev)continue;
			//子頂点sから木dpして、先に子頂点の情報を更新する
			self(self, s, v);
			if (c[v] == 'a') {
				m1 *= (dp[s][0] + dp[s][2]);
			}
			else {
				m1 *= (dp[s][1] + dp[s][2]);
			}
			m2 *= (dp[s][0] + dp[s][1] + 2 * dp[s][2]);
		}

		if (c[v] == 'a') {
			dp[v][0] = m1;
		}
		else {
			dp[v][1] = m1;
		}
		dp[v][2] = m2 - m1;
	};

	dfs(dfs, 0, -1);


	cout << dp[0][2].val() << endl;
	

	return 0;
}

Submission Info

Judge Result