Orange Boy Can You Solve It Out? Ep.13

思考题 on trees again

Tree

You are given a weighted undirected tree T of N nodes. Each edge i has a weight W_i.
Assume that the edges you need to travel from node i to j is
E_1,E_2,E_3...E_k then we define $c_{i,j}=(-1)^k \times \sum {i=0}^kW{E_i}For each node i, print\sum_{j=0}^nc_{j,i}$

Example

Tree={
1->2,2
1->3,3
2->4,1
2->5,4
}
Answer:
-4 2 13 -1 2
Explain:
tree
For node 1,0+2+3-6-3=-4
For node 2,2+0-5+1+4=2
For node 3,3-5+0+6+9=13
For node 4,-3+1+6+0-5=-1
For node 5,-6+4+9-5+0=2

Constriants

Subtask 1(10%):N<=1000
Subtask 2(90%):N\leq10^5

Orange Boy?

版权声明:
作者:XGN
链接:https://blog.hellholestudios.top/archives/195
来源:Hell Hole Studios Blog
文章版权归作者所有,未经允许请勿转载。

THE END
分享
二维码
< <上一篇
下一篇>>