A173976.救援分区
普及/提高-
官方
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
一片山区中有 n 个村庄,编号为 1 到 n。村庄之间有 n−1 条双向道路,任意两个村庄之间都恰好存在一条不重复经过村庄的路径。
第 i 个村庄有 pi 名居民,并可能设有医疗站和物资站:
- mi=1 表示该村庄设有医疗站,mi=0 表示没有;
- si=1 表示该村庄设有物资站,si=0 表示没有。
同一个村庄可以同时设有医疗站和物资站,也可以两种站点都没有。
救援队准备恰好封闭一条道路。封闭后,原来的道路网络会分成两个互不连通的区域,每个区域都由至少一个村庄组成。
为了让两个区域都能独立开展救援,每个区域都必须同时满足:
- 至少有一个村庄设有医疗站;
- 至少有一个村庄设有物资站。
如果一个村庄同时设有两种站点,那么它可以同时满足所在区域的这两项要求。
一个区域的人口总数等于该区域内所有村庄的居民数量之和。在满足站点要求的前提下,救援队希望两个区域的人口总数之差的绝对值尽可能小。
请你求出这个最小值。如果无论封闭哪条道路都无法满足要求,输出 −1。
输入格式
第一行输入一个整数 n,表示村庄数量。
接下来 n 行,第 i 行输入三个整数 pi,mi,si,分别表示第 i 个村庄的居民数量、是否设有医疗站、是否设有物资站。
接下来 n−1 行,每行输入两个整数 u,v,表示村庄 u 和村庄 v 之间有一条双向道路。
输出格式
输出一个整数,表示两个区域人口总数之差的绝对值的最小值。
如果不存在满足要求的方案,输出 −1。
输入输出样例
输入#1
6 5 1 0 8 0 0 4 0 1 7 0 0 6 1 0 10 0 1 1 2 2 3 2 4 4 5 4 6
输出#1
6
输入#2
3 10 1 0 20 0 1 30 0 0 1 2 2 3
输出#2
-1
说明/提示
样例解释 1
封闭村庄 2 与村庄 4 之间的道路后:
- 第一个区域包含村庄 1,2,3,人口总数为 5+8+4=17,村庄 1 有医疗站,村庄 3 有物资站;
- 第二个区域包含村庄 4,5,6,人口总数为 7+6+10=23,村庄 5 有医疗站,村庄 6 有物资站。
两个区域均满足要求,人口总数之差的绝对值为 ∣17−23∣=6。其他道路均不能产生满足站点要求的两个区域,因此答案为 6。
样例解释 2
所有村庄中一共只有一个医疗站和一个物资站,无法让两个互不连通的区域都同时拥有这两种站点。
数据范围
对于所有测试数据,保证:
- 2≤n≤2×105;
- 1≤pi≤109;
- mi,si∈{0,1};
- 1≤u,v≤n,且 u=v;
- 不存在连接同一对村庄的重复道路;
- 给出的 n−1 条道路将所有村庄连成一棵树;
- 不保证存在满足要求的分区方案。
输入解题思路,AI测评打分。不知道怎么写?