题目理解与建模

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

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

题目内容

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

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

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