玩一下csdn的markdown。 这道题的大意是
给定一棵树，两个相邻点之间的距离为 1 1 1，对于相邻距离为 2 2 2的点之间可以新建一条边，要求每个点到其他所有点点的距离之和的和。
看似是一道搜索题，但是我多日后再想起来感觉还有动态规划的思路在里头。
参考帖子：http://lexue.bit.edu.cn/mod/forum/discuss.php?d=126124，阅读前请先看一看这篇文章。
如果看不到原帖，这里大致概括本贴中用到的原帖中的结论，对于相邻的节点 i , j i,j i,j，原帖总结了所有节点中除了 i , j i,j i,j 外的任意节点 x x x 到 i i i 的距离 d d d 于到 j j j 的距离 d ′ d' d′ 之间的关系。
本文是对上贴中最后留白部分的推论，我写这个的时候程序还没写（主要是担心写不出ac，先写写推导过程拿一点平时分orz）
在zzxdl的帖子中两点之间的距离用 d i s t dist dist 表示，文中用 d d d 表示，且 d ( x , x ) = 0 , d ′ ( x , x ) = 0 d(x,x)=0,d'(x,x)=0 d(x,x)=0,d′(x,x)=0
对于图 G ( E , V ) G(E,V) G(E,V)，取一条边 i − j i-j i−j，边上的两点分别为 i , j i,j i,j，设节点 i i i 的所有子树编号为 1 , … , n 1,\ldots,n 1,…,n， j j j 节点所有子树编号为 1 , … , m 1,\ldots,m 1,…,m，对于 i i i 节点的第 k k k 个子树上所有节点的集合为 S i k S_{ik} Sik，其中所有到 i i i 距离为偶数的节点的集合为 E i k E_{ik} Eik ，距离为奇数的节点的集合为 O i k O_{ik} Oik。于节点 j j j 同理。
那么有： ⋃ k E j k = ⋃ k O i k − { j } ⋃ k O j k = ⋃ k E i k ∪ { i } \begin{aligned} \bigcup_k{E_{jk}}=\bigcup_k{O_{ik}}-\{j\}\\ \bigcup_k{O_{jk}}=\bigcup_k{E_{ik}}\cup\{i\}\\ \end{aligned} k⋃Ejk=k⋃Oik−{j}k⋃Ojk=k⋃Eik∪{i} 令： O i = ⋃ k O i k O j = ⋃ k O j k E i = ⋃ k E i k E j = ⋃ k E j k s u m i = ∑ u ≠ i d ′ ( u , i ) s u m j = ∑ u ≠ j d ′ ( u , j ) \begin{aligned} &O_i=\bigcup_k{O_{ik}} & O_j=\bigcup_k{O_{jk}}\\ &E_i=\bigcup_k{E_{ik}} & E_j=\bigcup_k{E_{jk}}\\ &sum_i=\sum_{u\neq i}{d'(u,i)}\\&sum_j=\sum_{u\neq j}{d'(u,j)} \end{aligned} Oi=k⋃OikEi=k⋃Eiksumi=u=i∑d′(u,i)sumj=u=j∑d′(u,j)Oj=k⋃OjkEj=k⋃Ejk 显然，结合上文的推导： s u m i = ∑ u ∈ E i d ′ ( u , i ) + ∑ u ∈ O i d ′ ( u , i ) s u m j = ∑ u ∈ E j d ′ ( u , j ) + ∑ u ∈ O j d ′ ( u , j ) = ∑ u ∈ O i − { j } d ′ ( u , j ) + ∑ u ∈ E i + { i } d ′ ( u , j ) = ∑ u ∈ O i d ′ ( u , j ) + ∑ u ∈ E i d ′ ( u , j ) + 1 \begin{aligned} sum_i&=\sum_{u\in E_i}{d'(u,i)}+\sum_{u\in O_i}{d'(u,i)}\\ sum_j&=\sum_{u\in E_j}{d'(u,j)}+\sum_{u\in O_j}{d'(u,j)}\\ &=\sum_{u\in O_i-\{j\}}{d'(u,j)}+\sum_{u\in E_i+\{i\}}{d'(u,j)}\\ &=\sum_{u\in O_i}{d'(u,j)}+\sum_{u\in E_i}{d'(u,j)}+1\\ \end{aligned} sumisumj=u∈Ei∑d′(u,i)+u∈Oi∑d′(u,i)=u∈Ej∑d′(u,j)+u∈Oj∑d′(u,j)=u∈Oi−{j}∑d′(u,j)+u∈Ei+{i}∑d′(u,j)=u∈Oi∑d′(u,j)+u∈Ei∑d′(u,j)+1 由于 ( i , j ) ∈ E (i,j)\in E (i,j)∈E，所以有且仅有唯一的 p ∈ { 1 , 2 … , n } p\in\{1,2\ldots,n\} p∈{1,2…,n}，使得其所对应的子树中所有点的集合满足： j ∈ S i p E i p + O i p = S i p \begin{aligned} j&\in S_{ip}\\ E_{ip}+O_{ip}&=S_{ip} \end{aligned} jEip+Oip∈Sip=Sip 那么： s u m j = ∑ u ∈ O i − O i p d ′ ( u , j ) + ∑ u ∈ E i − E i p d ′ ( u , j ) + 1 + ∑ u ∈ O i p d ′ ( u , j ) + ∑ u ∈ E i p d ′ ( u , j ) = ∑ u ∈ O i − O i p d ′ ( u , i ) + ∑ u ∈ E i − E i p d ′ ( u , i ) + 1 + ∣ E i ∣ − ∣ E i p ∣ + ∑ u ∈ O i p d ′ ( u , i ) − ∣ O i p ∣ + ∑ u ∈ E i p d ′ ( u , i ) = ∑ u ∈ E i d ′ ( u , i ) + ∑ u ∈ O i d ′ ( u , i ) + ∣ E i ∣ − ∣ S i p ∣ + 1 = s u m i + ∣ E i ∣ − ∣ S i p ∣ + 1 \begin{aligned} sum_j&=\sum_{u\in O_i-O_{ip}}{d'(u,j)}+\sum_{u\in E_i-E_{ip}}{d'(u,j)}+1+\sum_{u\in O_{ip}}{d'(u,j)}+\sum_{u\in E_{ip}}{d'(u,j)}\\ &=\sum_{u\in O_i-O_{ip}}{d'(u,i)}+\sum_{u\in E_i-E_{ip}}{d'(u,i)}+1+|E_i|-|E_{ip}|+\sum_{u\in O_{ip}}{d'(u,i)}-|O_{ip}|+\sum_{u\in E_{ip}}{d'(u,i)}\\ &=\sum_{u\in E_i}{d'(u,i)}+\sum_{u\in O_i}{d'(u,i)}+|E_i|-|S_{ip}|+1\\ &=sum_i+|E_i|-|S_{ip}|+1 \end{aligned} sumj=u∈Oi−Oip∑d′(u,j)+u∈Ei−Eip∑d′(u,j)+1+u∈Oip∑d′(u,j)+u∈Eip∑d′(u,j)=u∈Oi−Oip∑d′(u,i)+u∈Ei−Eip∑d′(u,i)+1+∣Ei∣−∣Eip∣+u∈Oip∑d′(u,i)−∣Oip∣+u∈Eip∑d′(u,i)=u∈Ei∑d′(u,i)+u∈Oi∑d′(u,i)+∣Ei∣−∣Sip∣+1=sumi+∣Ei∣−∣Sip∣+1
由此再进行一次深度优先搜索即可得到答案。
