【树边的和】

【问题描述】

树是指由n个点,n-1条边构成的联通无向图。如果有一棵树,它的每一条边(u,v)都有一个权值l(u,v),我们把这样的树称作带权树。

我们知道对于树上的任意两个点,他们之间的路径是唯一的。对于两个点u,v来说,我们可以算出u与v之间的路径上的所有边权之和,将其称作u与v之间路径的长度,记作d(u,v)。

你的任务是计算:∑d(u,v) (u!=v)

【输入文件】

输入文件的第一行为一个正整数n。

接下来的n-1行,每行三个非负整数x,y,w表示点x与点y之间有一条权值为w的一条边。

保证输入的图示一棵树。

【输出文件】

输出文件仅包含一行一个数,即答案。因为结果可能很大,请将答案模100 000 007输出

【输入样例】

4

1 2 4

1 3 4

1 4 4

【输出样例】

72

【样例解释】

d(1,2)+d(1,3)+d(1,4)=4+4+4=12

d(2,1)+d(2,3)+d(2,4)=4+8+8=20

d(3,1)+d(3,2)+d(3,4)=4+8+8=20

d(4,1)+d(4,2)+d(4,3)=4+8+8=20

ans=12+20+20+20=72

【数据范围】

n≤3×10^5 0≤w<1000000007

看n的范围肯定不能枚举……那么我们就换个角度,考虑每条边对答案的贡献!

首先随便选一个点作根,dfs出每个子树的size大小与deep深度,那么可以发现对于deep[v]=deep[u]+1的两点,他们之间的边l(u,v)在答案中会被选size[v]*(n-size[v])次,枚举每条边看看即可。最优因为点对是无序的,但是我们只是算了从u那一边选v,所以我们还要×2算从v那一边选u。

另外:本题DFS爆栈的脸黑……不过加上3句代码就可以放爆栈(OI中不能用!)

下面是代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*