A173976.救援分区

普及/提高-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

一片山区中有 nn 个村庄,编号为 11 到 nn。村庄之间有 n−1n-1 条双向道路,任意两个村庄之间都恰好存在一条不重复经过村庄的路径。

第 ii 个村庄有 pip_i 名居民,并可能设有医疗站和物资站:

  • mi=1m_i=1 表示该村庄设有医疗站,mi=0m_i=0 表示没有;
  • si=1s_i=1 表示该村庄设有物资站,si=0s_i=0 表示没有。

同一个村庄可以同时设有医疗站和物资站,也可以两种站点都没有。

救援队准备恰好封闭一条道路。封闭后,原来的道路网络会分成两个互不连通的区域,每个区域都由至少一个村庄组成。

为了让两个区域都能独立开展救援,每个区域都必须同时满足:

  • 至少有一个村庄设有医疗站;
  • 至少有一个村庄设有物资站。

如果一个村庄同时设有两种站点,那么它可以同时满足所在区域的这两项要求。

一个区域的人口总数等于该区域内所有村庄的居民数量之和。在满足站点要求的前提下,救援队希望两个区域的人口总数之差的绝对值尽可能小。

请你求出这个最小值。如果无论封闭哪条道路都无法满足要求,输出 −1-1。

输入格式

第一行输入一个整数 nn,表示村庄数量。

接下来 nn 行,第 ii 行输入三个整数 pi,mi,sip_i,m_i,s_i,分别表示第 ii 个村庄的居民数量、是否设有医疗站、是否设有物资站。

接下来 n−1n-1 行,每行输入两个整数 u,vu,v,表示村庄 uu 和村庄 vv 之间有一条双向道路。

输出格式

输出一个整数,表示两个区域人口总数之差的绝对值的最小值。

如果不存在满足要求的方案,输出 −1-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

封闭村庄 22 与村庄 44 之间的道路后:

  • 第一个区域包含村庄 1,2,31,2,3,人口总数为 5+8+4=175+8+4=17,村庄 11 有医疗站,村庄 33 有物资站;
  • 第二个区域包含村庄 4,5,64,5,6,人口总数为 7+6+10=237+6+10=23,村庄 55 有医疗站,村庄 66 有物资站。

两个区域均满足要求,人口总数之差的绝对值为 ∣17−23∣=6|17-23|=6。其他道路均不能产生满足站点要求的两个区域,因此答案为 66。

样例解释 2

所有村庄中一共只有一个医疗站和一个物资站,无法让两个互不连通的区域都同时拥有这两种站点。

数据范围

对于所有测试数据,保证:

  • 2≤n≤2×1052\le n\le 2\times 10^5;
  • 1≤pi≤1091\le p_i\le 10^9;
  • mi,si∈{0,1}m_i,s_i\in\{0,1\};
  • 1≤u,v≤n1\le u,v\le n,且 u≠vu\ne v;
  • 不存在连接同一对村庄的重复道路;
  • 给出的 n−1n-1 条道路将所有村庄连成一棵树;
  • 不保证存在满足要求的分区方案。

输入解题思路,AI测评打分。不知道怎么写?

首页