树学题

CF2063E

容易发现答案是

∑u,v∈T2min{depu−deplac(u,v),depv−deplac(u,v)}−1\sum_{u,v\in T}2min\{dep_u-dep_{lac(u,v)},dep_v-dep_{lac(u,v)}\}-1

且 u,vu,v 互不为祖先

∑u,v∈T2min{depu−deplac(u,v),depv−deplac(u,v)}−1=\sum_{u,v\in T}2min\{dep_u-dep_{lac(u,v)},dep_v-dep_{lac(u,v)}\}-1=

∑u,v∈T2min{depu,depv}−∑u,v∈T2deplac(u,v)−∑u,v∈T1\sum_{u,v\in T}2min\{dep_u,dep_v\}-\sum_{u,v\in T}2dep_{lac(u,v)}-\sum_{u,v\in T}1

分三段求：

第一段对depdep 从小到大排序，贡献是

2∗∑i=1ndepi∗(n−i)−2∗∑u∈T∑v∈sonudepu∗sizv2*\sum_{i=1}^{n}dep_i*(n-i)-2*\sum_{u \in T}\sum_{v \in son_u}dep_u*siz_v

第二段dfs枚举每个u的儿子，贡献是

2∗∑x,y∈sonusizx∗sizy∗depu=2*\sum_{x,y\in son_u}siz_x*siz_y*dep_u=

2∗∑v∈sonu(sizu−1−sizv)∗sizv∗depu2*\sum_{v \in son_u}(siz_u-1-siz_v)*siz_v*dep_u

第三段：

n(n−1)2−∑u∈T∑v∈sonudepu∗sizv\frac{n(n-1)}2-\sum_{u \in T}\sum_{v \in son_u}dep_u*siz_v