CVBB ACM Team

--- 2020-2021:teams:die_java:weeksummary11 [2020/08/21 15:16]
wxg [王兴罡]
+++ 2020-2021:teams:die_java:weeksummary11 [2020/08/21 16:23] (当前版本)
mychael
@@ 行 28: / 行 28: @@
 **hxm:**
-\\ **题目大意：**
+\\ **题目大意：** 给一棵树，每个点都有一种颜色，设$s(i,j)$为两点之间颜色种类数，求所有点对$s(i,j)$之和
-\\ **tag:**
+\\ **tag:** 点分治，差分
 \\ **做法:**
+点分治即可
-\\ **comment:**
+对于每棵分治出来的树，考虑过根的所有路径对树内点的影响
+首先单独考虑一种颜色的影响，从根节点出发到每棵子树的每个点u，u节点在该颜色下会产生贡献当且仅当u到根的路径上有该颜色的节点
+所以我们只要找出一个子树中所有颜色为该颜色，且其祖先中没有该颜色【也就是最高的该颜色点】，其子树所有点都会产生贡献，那么所有的对根的贡献就是所有这样点的子树大小之和
+考虑对子树内的点，就减去该子树的贡献，就转化为和根类似的了
+每当第一次经过一种颜色的点时，其子树内所有点经过该点必定产生该颜色的贡献，此时把该颜色的贡献改为剩余子树的大小即可
+还有，根节点的颜色特殊考虑
+写起来细节真的多
+\\ **comment:** 点分治练习
 ----
@@ 行 49: / 行 61: @@
 ====== 黄旭民 ======
-比赛：
+复习了点分治，整理了点分治模板
 \\