传统题 1000ms 256MiB

NOI 树

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给出一颗 nn 个结点的树,每个结点上有 NOI 三个字母其中一个。

一眼望去,树上有很多 NOI。一个"NOI三元组"定义为:三个分别为 NOI 的结点,且 O 结点在 N 结点和 I 结点之间的必经路径上。

你需要计算出 NOI 三元组的个数。由于答案可能很大,对 109+710^9+7 取模。

输入格式

第一行一个整数 nn,表示结点个数。结点编号为 1n1\ldots n

第二行由 nn 个大写字母 NOI 组成的字符串,依次表示每个结点上的字母。

接下来 n1n-1 行,每行两个整数 ui, viu_i,~v_i,表示树上的一条边,连接 uiu_iviv_i 两个结点。

输出格式

一行一个整数,表示 NOI 三元组的个数。由于答案可能很大,对 109+710^9+7 取模。

5
ONION
1 2
1 3
1 4
4 5
3

说明

对于 30%30\% 的数据,n100n \le 100

对于另外 30%30\% 的数据,ui+1=viu_i+1=v_i

对于 100%100\% 的数据,n105n\le 10^5

本题使用 Subtask

TTOI 暑假信心赛 Round 1 (Hydro Tritium Round #003)

未参加
状态
已结束
规则
IOI
题目
5
开始于
2021-8-27 14:00
结束于
2021-8-27 17:00
持续时间
3 小时
主持人
参赛人数
23