牛客病毒感染
题意:给出一颗所有路径都为1的树,让你找出到其余点距离和最小的点,若存在多个,都输出。
暴力法:跑n边迪杰斯特拉,n>=5e5,显然不行。
试着画图模拟找思路:
上图中,1到其余各点的距离和为7(1+1+1+1+1+2),2到其余各点的距离和为10(1+1+2+2+2+2),因为题目保证了各路径长度都为1,显然,从1到2的过程中,增加的路径是1、3、4、5、6五个点贡献的,减少的路径则是2、7两个点贡献的。也就是ans[2]=ans[1]+5-2。其中的5和2,就是结点2“左边”的结点数量和“右边”的节点数量。
这样一来,这个问题就分成了下面几个步骤:
- 计算出每个结点“左边”的结点数量和“右边”的节点数量。
- 我们用dfs递归到根结点,然后回溯累加即可。
- 计算出某个结点x的答案。
- 使用bfs计算x到其余结点的距离,累加。
- 通过结点x来递推其余结点 。
- 使用bfs转移。
AC代码:
1 | /* |