先梳理题意 & 核心思路
题目是一棵树上砍一条边,把树拆成两棵子树 A、B。
要求:
* A 里面 至少 1 个医疗站、至少 1 个物资站
* B 里面 至少 1 个医疗站、至少 1 个物资站
在合法的切割里,求 (|sumA - sumB|) 的最小值;无解输出 -1。
设:
* sumAll:整棵树总人口
* (subSum[x]):以 x 为根的子树人口和
* (subM[x]):子树 x 内医疗站总数
* (subS[x]):子树 x 内物资站总数
* totalM:全树医疗站总数
* totalS:全树物资站总数
切断父节点和子节点 v 这条边后:
* 子块:子树 vvv
✅ 合法条件:(subM[v]>=1, subS[v]>=1)(subM[v]>=1,\ subS[v]>=1)(subM[v]>=1, subS[v]>=1)
* 剩下大块:原树去掉子树 vvv
✅ 合法条件:(totalM−subM[v]>=1,totalS−subS[v]>=1)(totalM - subM[v] >=1,totalS - subS[v] >=1)(totalM−subM[v]>=1,totalS−subS[v]>=1)
只要同时满足上面四条,这个切割就是合法的,差值 = (∣sumAll−2∗subSum[v]∣)( | sumAll - 2 * subSum[v] | )(∣sumAll−2∗subSum[v]∣),我们取最小即可。
C++代码:
杂度说明
* O(n)O (n)O(n),每个点每条边遍历一次,完全满足 n=2∗105n = 2*10^5n=2∗105
* p[i]p [i]p[i] 可以到 1e91e91e9,全部用 longlonglong longlonglong,这点代码已经处理