Submission #60285195

---

Source Code Expand

#include<bits/stdc++.h>
#include"atcoder/all"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a) a.begin(),a.end()
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> P;
const ll mod=1000000007;
const ll inf=1ll<<61;
typedef modint1000000007 mi;

char c[100005];
vector<int>G[100005];
mi dp[3][100005];

void dfs(int now,int par){
	mi all_children=1,same=1;
	for(auto e:G[now]){
		if(e==par)continue;
		dfs(e,now);
		all_children*=(dp[0][e]+dp[1][e]+2*dp[2][e]);
		if(c[now]=='a')same*=dp[0][e]+dp[2][e];
		else same*=dp[1][e]+dp[2][e];
	}
	all_children-=same;
	dp[c[now]-'a'][now]=same;
	dp[2][now]=all_children;
}

int main(){
	int n;cin>>n;
	rep(i,n)cin>>c[i];
	rep(i,n-1){
		int a,b;
		cin>>a>>b;
		a--;b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	dfs(0,-1);
	cout<<dp[2][0].val()<<endl;
}

Submission Info

Judge Result