题面 P4297 [NOI2006]网络收费 Solution 这题喵啊。 首先,我们会发现统计两个点互相的贡献是一个极其困难的问题。 但是,仔细观察那张收费表格后会发现,我们可以重新定义一下这个收费:我们假设路由器节点的颜色为叶子中数目较多的颜色,当一个叶子结点颜色与路由器节点颜色相同的时候不收钱,否则收一份钱。我们可以惊讶的发现,这样做之后我们的新收费做法就与原来题目要求的重合了,而且贡献由点对转到了点上。 接下来,我们就可以统计每个叶子节点对每个路由器产生的贡献了。我们设$F[i][j]$表示第$i$个叶子节…