题目理解与建模

给一棵共有 n 个结点的树，每个结点初始标签为 d / p / ?。 一次操作可以把任意结点的标签改为 d 或 p，每次改动计 1 次。 目标：通过最少的重绘，使

1. 所有结点最终均为 d 或 p；
2. 每条边两端标签不同（相邻异色）。 输出最少需要的重绘次数。

题目内容

给定一棵有$n$个节点的树，节点编号为1到$n$。每个节点带有一个字符标签$s_i$，仅可为$d、p$或$?$。

你可以对任意节点进行重绘操作，将其标签修改为$d$或$p$。每次重绘操作均计为一次修改。

请你找到一组重绘方案，使得最终所有的标签都是$d$或$p$，并且每条边连接的两个节点标签均不相同，并使得重绘次数最少。输出最少的重绘次数。

输入描述

第一行输入一个整数$n(2≦n≦2×10^5)$,表示树的节点数。

第二行输入一个长度为$n$的字符串$s$，仅包含字符$d、p$和$?$，表示节点$1$到$n$的初始标签序列。

接下来$n-1$行，每行输入两个整数$u_i$和$v_i$$(1≦u_i,v_i≦n;u_i≠v_i)$,表示节点$u_i$与$v_i$之间存在一条无向边。

输出描述

输出一个整数，表示最小重绘次数。

样例1

输入

5
?d?pp
1 2
2 3
2 4
4 5

输出

3

说明

原标签序列为$?d?pp$；一种最优重绘方案为将节点$1$重绘为$P$，节点$3$重绘为$P$，节点$5$重绘为$d$,得到标签$pdppd$;

最少重绘次数为$3$。

样例2

输入

4
dddd
1 2
2 3
3 4

输出

2