A7169 | $雾港学宫的能量点对$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

给定一棵包含 $n$ 个点的无向树 $T=(V,E)$，点编号为 $1,2,\dots,n$。树中任意两点之间的简单路径唯一。 每条边 $e\in E$ 带有一个整数权值（能量标记）$c_e$。对任意两点 $u,v$，设 $P(u,v)$ 表示从 $u$ 到 $v$ 的唯一简单路径所包含的边集合，则定义路径的“能量奇偶性”为 $$ p(u,v)=\left(\sum_{e\in P(u,v)}c_e\right)\bmod2. $$ 你需要统计满足 $$ p(u,v)=0 $$ 的无序点对数量，即点对 $(u,v)$ 满足 $1\le u<v\le n$ 且路径边权和为偶数的点对数。

第一行一个整数 $n$。 接下来 $n-1$ 行，每行三个整数 $u,v,c$，表示存在一条无向边连接点 $u$ 与点 $v$，其权值为 $c$。

输出一个整数，表示满足条件的无序点对数量。

输入 #1

输出 #1

样例1解释 说明：例如 $P(1,5)$ 为边 $(1,2),(2,4),(4,5)$，其权值和为 $1+3+4=8$，因此 $$ p(1,5)=8\bmod2=0, $$ 该点对计入答案。 数据范围与测试点 * $1\le n\le200000$ * $|c|\le10^9$ 测试点分层（只给编号范围与 $n$ 上界）： 测试点编号$n$ 上界$1\sim4$$n\le20$$5\sim10$$n\le10000$$11\sim20$$n\le200000$

C++ 编辑器

输入

输出