CF260D Black and White Tree
题目描述
存在一棵 $n$ 个节点的树,树边有**非负整数**边权,每个节点都有颜色,且只可能是黑色或白色(用 $0$ 或 $1$ 表示)。原树不存在树边连接 $2$ 个同色的节点。
现给出每个节点的颜色和与这个节点相连的边的权值和,请您还原这棵树。
输入格式
第一行一个整数 $n$ $(2\le n\le10^5)$,表示节点数。
第 $2$ ~ $n+1$ 行,每行两个整数 $c_{i}$ , $s_{i}$ $(0\le c_i\le1,0\le s_i\le10^9)$ ,表示节点 $i$ 的颜色和与节点 $i$ 相连的边的权值和。
输出格式
共输出 $n-1$ 行,每行 $u,v,w$ ( 你需要保证 $1\le u,v\le n,0\le w\le10^9$ ),代表这条边的左右端点和权值。
如果存在多组解,输出任意一组即可。
输入数据保证至少存在一个符合要求的图。