现在有nnn个炉石玩家被挂在一棵有根树上,树根节点的标号是111.树是一种有nnn个点且有n1n - 1n1条边的结构, 并且一棵树保证没有环. nnn个点的每个点上都有一个炉石玩家,并且每个炉石玩家都有一个战力值为aia_iai.对于树上的每一位炉石玩家,都有一棵属于他的子树,我们定义两个节点之间的距离为两个节点之间最短路径经过的边数.对于一个给定的值kkk,如果满足dis(i,j)=
现在有nnn个炉石玩家被挂在一棵有根树上,树根节点的标号是111.树是一种有nnn个点且有n−1n - 1n−1条边的结构, 并且一棵树保证没有环. nnn个点的每个点上都有一个炉石玩家,并且每个炉石玩家都有一个战力值为aia_iai.对于树上的每一位炉石玩家,都有一棵属于他的子树,我们定义两个节点之间的距离为两个节点之间最短路径经过的边数.对于一个给定的值kkk,如果满足dis(i,j)=kdis(i, j) = kdis(i,j)=k,我们就说iii和jjj旗鼓相当.dis(i,j)dis(i,j)dis(i,j)表示树上节点iii通过最短的路径到达节点jjj所经过的边的数量. 现在需要统计每个炉石玩家的ratingratingrating值,ratingratingrating值的计算方式是这样的,对于炉石玩家uuu的子树中的所有节点,如果x,yx, yx,y是旗鼓相当的,并且x,yx,yx,y的最近公共祖先是uuu且满足u≠x & u≠yu neq x , & , u neq yu=x&u=y,那么uuu的ratingratingrating就会增加ax+aya_x + a_yax+ay.