题目内容

小塔有一颗$n$个点的树。如果树上存在一个点$w$，使得原始的树上存在边$(u,w)$和$(w,v)$，那么我们可以添加一条边$(u,v)$.

小塔想知道，添加若干条边之后，树上任意两点之间的距离之和最少是多少。即求$\sum_{i=1}^{n}\sum_{j=1}^{n}dist(i,j)$ 。

输入描述

思路

按照题目描述实际添加的边只有以上两种，这里称之为横边与竖边，我们先求出在没有两条边的情况下的距离之和，观察可得，每经过一条横或竖边总距离之和便可减1，所以分别求这两条边的贡献，同时视情况，下面可以借助竖边快速的向上跳跃，并且任意一个点若要通过除其父节点的子树外其他节点必然走竖边，在这种情况下我们可以直接计算此条竖边的贡献，并且动态的将此点看作已经向上跳跃到其父节点的父节点，在整个树中，向上跳跃到同一个节点的所有点去往除子树外所有节点均为同一种情况，所以可以使用递归对跳跃的节点进行统计，并同时计算此子树内边的竖边与横边的贡献值，进行树形操作。

所以两总边贡献统计操作，一条由a向上到c的竖边贡献为跳跃到a的节点数与除a的父节点的子树所有节点外的节点数相乘，此条竖边统计完，节点可进行跳跃操作并统计，一个节点a之下所有直接相连的子节点之间的横边便是任意一个子节点的跳跃节点数与所有子节点的跳跃子节点数减去当前子节点的跳跃子节点数。 总体思想为以竖边为主将节点动态的看待，由下至上进行树形操作。

代码

C++