You are given a tree (an undirected connected acyclic graph) consisting of $n$ vertices and $n - 1$ edges. A number is written on each edge, each number is either $0$ (let's call such edges $0$-edges) or $1$ (those are $1$-edges).

Let's call an ordered pair of vertices $(x, y)$ ($x \ne y$) valid if, while traversing the simple path from $x$ to $y$, we never go through a $0$-edge after going through a $1$-edge. Your task is to calculate the number of valid pairs in the tree.


-----Input-----

The first line contains one integer $n$ ($2 \le n \le 200000$) — the number of vertices in the tree.

Then $n - 1$ lines follow, each denoting an edge of the tree. Each edge is represented by three integers $x_i$, $y_i$ and $c_i$ ($1 \le x_i, y_i \le n$, $0 \le c_i \le 1$, $x_i \ne y_i$) — the vertices connected by this edge and the number written on it, respectively.

It is guaranteed that the given edges form a tree.


-----Output-----

Print one integer — the number of valid pairs of vertices.


-----Example-----
Input
7
2 1 1
3 2 0
4 2 1
5 2 0
6 7 1
7 2 1

Output
34



-----Note-----

The picture corresponding to the first example:

[Image]

Difficulty: HARD
Tags: Graph traversal

Tree algorithms

Dynamic programming

Divide and conquer

Spanning trees
Skill types: Dynamic programming

Starter code:

Solutions:
from collections import deque
from sys import stdin

def bfs(source, graph, mark, fcount):
	visited = [source]
	q = deque()
	mark[source] = True
	q.append(source)
	while q:
		u = q.popleft()
		for v in graph[u]:
			if not mark[v]:
				mark[v] = True
				visited.append(v)
				q.append(v)
	for u in visited:
		fcount[u] = len(visited)

def main():
	n = int(stdin.readline())
	g = [[[] for _ in range(0, n)] for _ in range(0, 2)]
	cnt = [[0 for _ in range(0, n)] for _ in range(0, 2)]
	for line in stdin.readlines():
		(u, v, c) = map(int, line.split())
		g[c][u - 1].append(v - 1)
		g[c][v - 1].append(u - 1)
	res = 0
	for link in range(0, 2):
		mark = [False] * n
		for u in range(0, n):
			if not mark[u] and len(g[link][u]) > 0:
				bfs(u, g[link], mark, cnt[link])
				res += cnt[link][u] * (cnt[link][u] - 1)
	for i in range(0, n):
		if cnt[0][i] > 0 and cnt[1][i] > 1:
			res += (cnt[0][i] - 1) * (cnt[1][i] - 1)
	print(int(res))
main()


def process(e):
	answer = 0
	graphs = [{}, {}]

	def find_root(x, i):
		g = graphs[i]
		L = []
		while x != g[x]:
			L.append(x)
			x = g[x]
		for y in L:
			g[y] = x
		return x
	for (a, b, w) in e:
		g = graphs[w]
		if a not in g and b not in g:
			g[a] = min(a, b)
			g[b] = min(a, b)
		elif b not in g:
			a2 = find_root(a, w)
			g[b] = a2
		elif a not in g:
			b2 = find_root(b, w)
			g[a] = b2
		else:
			a2 = find_root(a, w)
			b2 = find_root(b, w)
			g[a2] = min(a2, b2)
			g[b2] = min(a2, b2)
	roots = [{}, {}]
	for i in range(2):
		for x in graphs[i]:
			x2 = find_root(x, i)
			if x2 not in roots[i]:
				roots[i][x2] = 0
			roots[i][x2] += 1
		for x in roots[i]:
			answer += roots[i][x] * (roots[i][x] - 1)
	for x in graphs[0]:
		if x in graphs[1]:
			x1 = find_root(x, 0)
			x2 = find_root(x, 1)
			answer += (roots[0][x1] - 1) * (roots[1][x2] - 1)
	return answer
n = int(input())
e = []
for i in range(n - 1):
	(a, b, w) = [int(x) for x in input().split()]
	e.append([a, b, w])
print(process(e))


import sys
input = sys.stdin.readline
n = int(input())
abd = [list(map(int, input().split())) for i in range(n - 1)]
graph = [[] for i in range(n + 1)]
deg = [0] * (n + 1)
if n == 2:
	print(2)
	return
for (a, b, d) in abd:
	graph[a].append((b, d))
	graph[b].append((a, d))
	deg[a] += 1
	deg[b] += 1
dp = [[0] * 3 for i in range(n + 1)]
stack = []
root = 0
for i in range(1, n + 1):
	if deg[i] == 1:
		stack.append(i)
	elif not root:
		root = i
		deg[root] += 1
while stack:
	x = stack.pop()
	if dp[x][0] == dp[x][1] == 0:
		for (y, d) in graph[x]:
			dp[y][d] += 1
			deg[y] -= 1
			if deg[y] == 1:
				stack.append(y)
	else:
		for (y, d) in graph[x]:
			if deg[y] > 1:
				dp[y][d] += dp[x][d] + 1
				if d == 1:
					dp[y][2] += dp[x][0] + dp[x][2]
				deg[y] -= 1
				if deg[y] == 1:
					stack.append(y)
stack = [root]
deg[root] -= 1
while stack:
	x = stack.pop()
	for (y, d) in graph[x]:
		if deg[y] == 1:
			deg[y] -= 1
			dp[y][d] += dp[x][d] - dp[y][d]
			if d == 1:
				dp[y][2] += dp[x][2] + dp[x][0] - dp[y][0] - dp[y][2]
			stack.append(y)
ans = 0
for (i, j, k) in dp:
	ans += i + j + k
print(ans)


import collections as cc
import itertools as it
import bisect as bi
import sys
sys = sys.stdin.readline
I = lambda : list(map(int, input().split()))

def find(x, i):
	while x != parent[i][x]:
		x = parent[i][x]
	return x

def union(x, y, i):
	a = find(x, i)
	b = find(y, i)
	parent[i][a] = parent[i][b] = min(a, b)
	if min(a, b) == a:
		sz[i][a] += sz[i][b]
	else:
		sz[i][b] += sz[i][a]
(n,) = I()
parent = [[i for i in range(n + 1)] for j in range(2)]
sz = [[1 for i in range(n + 1)] for j in range(2)]
for i in range(n - 1):
	t = I()
	union(*t)
ans = 0
for i in range(1, n + 1):
	if parent[0][i] == i:
		ans += sz[0][i] * (sz[0][i] - 1)
	if parent[1][i] == i:
		ans += sz[1][i] * (sz[1][i] - 1)
	ans += (sz[0][find(i, 0)] - 1) * (sz[1][find(i, 1)] - 1)
print(ans)


import os
import sys
from io import BytesIO, IOBase
import string
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class DSU:

	def __init__(self, nodes):
		self.p = [i for i in range(nodes)]
		self.r = [0 for i in range(nodes)]
		self.s = [1 for i in range(nodes)]

	def nonrecurive_get(self, u):
		v = u
		while self.p[v] != v:
			v = self.p[v]
		while self.p[u] != u:
			(u, self.p[u]) = (self.p[u], v)
		return u

	def get(self, u):
		if u != self.p[u]:
			self.p[u] = self.get(self.p[u])
		return self.p[u]

	def union(self, u, v):
		u = self.get(u)
		v = self.get(v)
		if u != v:
			if self.r[u] > self.r[v]:
				(u, v) = (v, u)
			self.p[u] = v
			if self.r[u] == self.r[v]:
				self.r[v] += 1
			self.s[v] += self.s[u]

	def size(self, u):
		u = self.get(u)
		return self.s[u]

def solve():
	n = int(input())
	dsus = [DSU(n), DSU(n)]
	for edge in range(n - 1):
		(x, y, c) = [int(s) for s in input().split(' ')]
		dsus[c].union(x - 1, y - 1)
	return sum([dsus[0].size(v) * dsus[1].size(v) - 1 for v in range(n)])
print(solve())


class dsu:

	def __init__(self, n):
		self.arr = [i for i in range(n)]
		self.size = [1 for i in range(n)]
		self.s = n

	def find(self, i):
		while i != self.arr[i]:
			i = self.arr[i]
		return i
		if self.arr[i] != i:
			self.arr[i] = self.find(self.arr[i])
		return self.arr[i]

	def union(self, i, j):
		fa = self.find(i)
		fb = self.find(j)
		if fa == fb:
			return
		s1 = self.size[fa]
		s2 = self.size[fb]
		if s1 < s2:
			self.arr[fa] = fb
			self.size[fb] += self.size[fa]
		else:
			self.arr[fb] = fa
			self.size[fa] += self.size[fb]
n = int(input())
zero = dsu(n)
one = dsu(n)
for i in range(n - 1):
	a = [int(i) for i in input().split(' ')]
	x = a[0] - 1
	y = a[1] - 1
	c = a[2]
	if c == 0:
		zero.union(x, y)
	else:
		one.union(x, y)
count = 0
for i in range(n):
	if zero.arr[i] == i:
		count += zero.size[i] * (zero.size[i] - 1)
	if one.arr[i] == i:
		count += one.size[i] * (one.size[i] - 1)
	count += (zero.size[zero.find(i)] - 1) * (one.size[one.find(i)] - 1)
print(count)


import sys
input = sys.stdin.readline

class UnionFind:

	def __init__(self, n):
		self.parent = [-1] * n
		self.cnt = n

	def root(self, x):
		if self.parent[x] < 0:
			return x
		else:
			self.parent[x] = self.root(self.parent[x])
			return self.parent[x]

	def merge(self, x, y):
		x = self.root(x)
		y = self.root(y)
		if x == y:
			return
		if self.parent[x] > self.parent[y]:
			(x, y) = (y, x)
		self.parent[x] += self.parent[y]
		self.parent[y] = x
		self.cnt -= 1

	def is_same(self, x, y):
		return self.root(x) == self.root(y)

	def get_size(self, x):
		return -self.parent[self.root(x)]

	def get_cnt(self):
		return self.cnt
n = int(input())
info = [list(map(int, input().split())) for i in range(n - 1)]
uf0 = UnionFind(n)
uf1 = UnionFind(n)
tree0 = [[] for i in range(n)]
tree1 = [[] for i in range(n)]
for i in range(n - 1):
	(a, b, cost) = info[i]
	a -= 1
	b -= 1
	if cost == 0:
		tree0[a].append(b)
		tree0[b].append(a)
		uf0.merge(a, b)
	else:
		tree1[a].append(b)
		tree1[b].append(a)
		uf1.merge(a, b)
ans0 = [0] * n
ans1 = [0] * n
for i in range(n):
	ans0[i] = uf0.get_size(i) - 1
	ans1[i] = uf1.get_size(i) - 1
ans = 0
for i in range(n):
	ans += ans0[i]
	ans += ans1[i]
	ans += ans0[i] * ans1[i]
print(ans)


import sys
from array import array
import typing as Tp

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

class UnionFind(object):
	__slots__ = ['nodes']

	def __init__(self, n: int):
		self.nodes = [-1] * n

	def size(self, x: int) -> int:
		return -self.nodes[self.find(x)]

	def find(self, x: int) -> int:
		if self.nodes[x] < 0:
			return x
		else:
			self.nodes[x] = self.find(self.nodes[x])
			return self.nodes[x]

	def unite(self, x: int, y: int) -> bool:
		(root_x, root_y, nodes) = (self.find(x), self.find(y), self.nodes)
		if root_x != root_y:
			if nodes[root_x] > nodes[root_y]:
				(root_x, root_y) = (root_y, root_x)
			nodes[root_x] += nodes[root_y]
			nodes[root_y] = root_x
		return root_x != root_y

def main():
	n = int(input())
	adj = [[] for _ in range(n)]
	(union0, union1) = (UnionFind(n), UnionFind(n))
	for (u, v, c) in (map(int, input().split()) for _ in range(n - 1)):
		adj[u - 1].append((v - 1, c))
		adj[v - 1].append((u - 1, c))
		if c == 0:
			union0.unite(u - 1, v - 1)
		else:
			union1.unite(u - 1, v - 1)
	ans = 0
	for i in range(n):
		(size0, size1) = (union0.size(i), union1.size(i))
		if union0.find(i) == i:
			ans += size0 * (size0 - 1)
		if union1.find(i) == i:
			ans += size1 * (size1 - 1)
		ans += (size0 - 1) * (size1 - 1)
	print(ans)
main()


import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.read
ns = lambda : readline().rstrip()
ni = lambda : int(readline().rstrip())
nm = lambda : map(int, readline().split())
nl = lambda : list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

class UnionFind:

	def __init__(self, n):
		self.ps = [-1] * (n + 1)

	def find(self, x):
		if self.ps[x] < 0:
			return x
		else:
			self.ps[x] = self.find(self.ps[x])
			return self.ps[x]

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return False
		if self.ps[x] > self.ps[y]:
			(x, y) = (y, x)
		self.ps[x] += self.ps[y]
		self.ps[y] = x
		return True

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def size(self, x):
		x = self.find(x)
		return -self.ps[x]

def solve():
	n = ni()
	uni = [UnionFind(n), UnionFind(n)]
	for _ in range(n - 1):
		(u, v, c) = nm()
		u -= 1
		v -= 1
		uni[c].unite(u, v)
	ans = 0
	for c in range(2):
		for i in range(n):
			if uni[c].find(i) == i:
				v = uni[c].size(i)
				ans += v * (v - 1)
	for i in range(n):
		ans += (uni[0].size(i) - 1) * (uni[1].size(i) - 1)
	print(ans)
	return
solve()


import sys
input = sys.stdin.readline

class DSU:

	def __init__(self, nodes):
		self.p = [i for i in range(nodes)]
		self.r = [0 for i in range(nodes)]
		self.s = [1 for i in range(nodes)]

	def nonrecurive_get(self, u):
		v = u
		while self.p[v] != v:
			v = self.p[v]
		while self.p[u] != u:
			(u, self.p[u]) = (self.p[u], v)
		return u

	def get(self, u):
		if u != self.p[u]:
			self.p[u] = self.get(self.p[u])
		return self.p[u]

	def union(self, u, v):
		u = self.get(u)
		v = self.get(v)
		if u != v:
			if self.r[u] > self.r[v]:
				(u, v) = (v, u)
			self.p[u] = v
			if self.r[u] == self.r[v]:
				self.r[v] += 1
			self.s[v] += self.s[u]

	def size(self, u):
		u = self.get(u)
		return self.s[u]

def solve():
	n = int(input())
	dsus = [DSU(n), DSU(n)]
	for edge in range(n - 1):
		(x, y, c) = [int(s) for s in input().split(' ')]
		dsus[c].union(x - 1, y - 1)
	S = 0
	for v in range(n):
		S += dsus[0].size(v) * dsus[1].size(v) - 1
	return S
print(solve())


import sys

class Disjoint:

	def __init__(self, n):
		self.n = n
		self.size = [1] * self.n
		self.parent = [i for i in range(self.n)]

	def root(self, node):
		self.parent[node] = node if self.parent[node] == node else self.root(self.parent[node])
		return self.parent[node]

	def join(self, a, b):
		a = self.root(a)
		b = self.root(b)
		if a == b:
			return False
		if self.size[a] > self.size[b]:
			(a, b) = (b, a)
		self.size[b] += self.size[a]
		self.parent[a] = b
		return True
inp = [int(x) for x in sys.stdin.read().split()]
n = inp[0]
white = Disjoint(n)
black = Disjoint(n)
inp_idx = 1
for i in range(n - 1):
	(x, y, c) = (inp[inp_idx], inp[inp_idx + 1], inp[inp_idx + 2])
	x -= 1
	y -= 1
	inp_idx += 3
	if c == 0:
		white.join(x, y)
	else:
		black.join(x, y)
ans = 0
for i in range(n):
	rootW = white.root(i)
	rootB = black.root(i)
	ans += white.size[rootW] - 1
	ans += black.size[rootB] - 1
	ans += (white.size[rootW] - 1) * (black.size[rootB] - 1)
print(ans)


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
import time
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string
start_time = time.time()

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]

def isInt(s):
	return '0' <= s[0] <= '9'
MOD = 10 ** 9 + 7

def solve():
	N = getInt()

	def find(a):
		if a != p[a]:
			p[a] = find(p[a])
		return p[a]

	def find2(a):
		if a != p2[a]:
			p2[a] = find2(p2[a])
		return p2[a]

	def union(a, b):
		(a, b) = (find(a), find(b))
		if a == b:
			return
		if size[a] > size[b]:
			(a, b) = (b, a)
		p[a] = b
		size[b] += size[a]

	def union2(a, b):
		(a, b) = (find2(a), find2(b))
		if a == b:
			return
		if size2[a] > size2[b]:
			(a, b) = (b, a)
		p2[a] = b
		size2[b] += size2[a]
	p = [i for i in range(N)]
	size = [1] * N
	p2 = [i for i in range(N)]
	size2 = [1] * N
	for _ in range(N - 1):
		(x, y, c) = getInts()
		x -= 1
		y -= 1
		if c == 1:
			union(x, y)
		else:
			union2(x, y)
	counts = [0] * N
	counts2 = [0] * N
	ans = 0
	for n in range(N):
		counts[find(n)] += 1
		counts2[find2(n)] += 1
	for n in range(N):
		ans += counts[n] * (counts[n] - 1)
		ans += counts2[n] * (counts2[n] - 1)
		ans += (counts2[p2[n]] - 1) * (counts[p[n]] - 1)
	return ans
print(solve())


def addEdge(arr: [], x, y):
	(x, y) = (getRoot(arr, x), getRoot(arr, y))
	if arr[x] <= arr[y]:
		arr[x] += arr[y]
		arr[y] = x
	else:
		arr[y] += arr[x]
		arr[x] = y

def getRoot(arr: [], id):
	while arr[id] > 0:
		id = arr[id]
	return id

def solve(zeroArr: [], oneArr: []):
	Ans = 0
	for i in range(1, len(zeroArr)):
		if zeroArr[i] < 0:
			Ans += zeroArr[i] * -1 * (zeroArr[i] * -1 - 1)
		if oneArr[i] < 0:
			Ans += oneArr[i] * -1 * (oneArr[i] * -1 - 1)
		if zeroArr[i] != -1 and oneArr[i] != -1:
			(one, zero) = (getRoot(oneArr, i), getRoot(zeroArr, i))
			Ans += (oneArr[one] * -1 - 1) * (zeroArr[zero] * -1 - 1)
	return Ans
n = int(input())
(zeroArr, oneArr) = ([-1] * (n + 1), [-1] * (n + 1))
while n > 1:
	(a, b, w) = [int(x) for x in input().split()]
	if w == 0:
		addEdge(zeroArr, a, b)
	else:
		addEdge(oneArr, a, b)
	n -= 1
print(solve(zeroArr, oneArr))


from collections import deque

def bfs(source, graph, mark, num, fcount):
	visited = [source]
	q = deque()
	mark[source] = True
	q.append(source)
	while q:
		u = q.popleft()
		for (v, c) in g[u]:
			if c == num and (not mark[v]):
				mark[v] = True
				visited.append(v)
				q.append(v)
	if len(visited) > 1:
		for u in visited:
			fcount[u] = len(visited)
n = int(input())
edges = [tuple(map(int, input().split())) for _ in range(0, n - 1)]
g = [[] for _ in range(0, n)]
cnt = [[0 for _ in range(0, n)] for _ in range(0, 2)]
for (u, v, c) in edges:
	g[u - 1].append((v - 1, c))
	g[v - 1].append((u - 1, c))
res = 0
for link in range(0, 2):
	mark = [False] * n
	for u in range(0, n):
		if not mark[u]:
			bfs(u, g, mark, link, cnt[link])
			res += cnt[link][u] * (cnt[link][u] - 1)
for i in range(0, n):
	if cnt[0][i] > 0 and cnt[1][i] > 1:
		res += (cnt[0][i] - 1) * (cnt[1][i] - 1)
print(int(res))


class UnionFind:

	def __init__(self, N):
		self.par = [i for i in range(N)]
		self.rank = [1 for i in range(N)]
		self.rank[0] = 0

	def union(self, x, y):
		if not self.is_same_set(x, y):
			par_x = self.find_par(x)
			par_y = self.find_par(y)
			if self.rank[par_x] > self.rank[par_y]:
				self.rank[par_x] += self.rank[par_y]
				self.rank[par_y] = 0
				self.par[par_y] = par_x
			else:
				self.rank[par_y] += self.rank[par_x]
				self.rank[par_x] = 0
				self.par[par_x] = par_y

	def find_par(self, x):
		if self.par[x] == x:
			return x
		self.par[x] = self.find_par(self.par[x])
		return self.par[x]

	def is_same_set(self, x, y):
		return self.find_par(x) == self.find_par(y)

	def size(self, x):
		return self.rank[self.find_par(x)]
n = int(input())
adj = [[] for i in range(n + 1)]
uf0 = UnionFind(n + 1)
uf1 = UnionFind(n + 1)
for i in range(n - 1):
	(x, y, c) = map(int, input().split())
	if c == 0:
		uf0.union(x, y)
	else:
		uf1.union(x, y)
	adj[x].append(y)
	adj[y].append(x)
	uf0.find_par(x)
	uf1.find_par(y)
resp = 0
resp += sum(map(lambda i: uf0.rank[i] * (uf0.rank[i] - 1), set(uf0.par)))
resp += sum(map(lambda i: uf1.rank[i] * (uf1.rank[i] - 1), set(uf1.par)))
for i in range(len(uf0.par)):
	if uf0.rank[uf0.find_par(i)] > 1:
		if uf1.rank[uf1.find_par(i)] > 1:
			resp += (uf0.rank[uf0.find_par(i)] - 1) * (uf1.rank[uf1.find_par(i)] - 1)
print(resp)


import sys
sys.setrecursionlimit(10 ** 9)

class UnionFind:

	def __init__(self, n):
		self.n = [-1] * n
		self.r = [0] * n
		self.siz = n

	def find_root(self, x):
		if self.n[x] < 0:
			return x
		else:
			self.n[x] = self.find_root(self.n[x])
			return self.n[x]

	def unite(self, x, y):
		x = self.find_root(x)
		y = self.find_root(y)
		if x == y:
			return
		elif self.r[x] > self.r[y]:
			self.n[x] += self.n[y]
			self.n[y] = x
		else:
			self.n[y] += self.n[x]
			self.n[x] = y
			if self.r[x] == self.r[y]:
				self.r[y] += 1
		self.siz -= 1

	def root_same(self, x, y):
		return self.find_root(x) == self.find_root(y)

	def count(self, x):
		return -self.n[self.find_root(x)]

	def size(self):
		return self.siz
n = int(input())
ouf = UnionFind(n)
zuf = UnionFind(n)
for _ in range(n - 1):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	if c == 0:
		zuf.unite(a, b)
	else:
		ouf.unite(a, b)
ans = 0
for i in range(n):
	m = zuf.count(i)
	if zuf.find_root(i) == i:
		ans += m * (m - 1)
	mm = ouf.count(i)
	if ouf.find_root(i) == i:
		ans += mm * (mm - 1)
	ans += (m - 1) * (mm - 1)
print(ans)


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	from collections import deque
	input = sys.stdin.readline

	class UnionFind:

		def __init__(self, n):
			self.n = n
			self.root = [-1] * (n + 1)
			self.rnk = [0] * (n + 1)

		def find_root(self, x):
			while self.root[x] >= 0:
				x = self.root[x]
			return x

		def unite(self, x, y):
			x = self.find_root(x)
			y = self.find_root(y)
			if x == y:
				return
			elif self.rnk[x] > self.rnk[y]:
				self.root[x] += self.root[y]
				self.root[y] = x
			else:
				self.root[y] += self.root[x]
				self.root[x] = y
				if self.rnk[x] == self.rnk[y]:
					self.rnk[y] += 1

		def isSameGroup(self, x, y):
			return self.find_root(x) == self.find_root(y)

		def size(self, x):
			return -self.root[self.find_root(x)]
	N = int(input())
	adj = [[] for _ in range(N + 1)]
	UF0 = UnionFind(N + 1)
	UF1 = UnionFind(N + 1)
	for _ in range(N - 1):
		(a, b, c) = map(int, input().split())
		adj[a].append((b, c))
		adj[b].append((a, c))
		if c == 0:
			UF0.unite(a, b)
		else:
			UF1.unite(a, b)
	ans = 0
	roots = set()
	for v in range(1, N + 1):
		r = UF1.find_root(v)
		if r not in roots:
			roots.add(r)
			s = -UF1.root[r]
			ans += s * (s - 1)
	roots = set()
	for v in range(1, N + 1):
		r = UF0.find_root(v)
		if r not in roots:
			roots.add(r)
			s = -UF0.root[r]
			ans += s * (s - 1)
	for v in range(1, N + 1):
		W = 0
		B = 0
		flg0 = 0
		flg1 = 0
		for (u, c) in adj[v]:
			if flg0 and flg1:
				break
			if c == 0:
				if flg0:
					continue
				W += UF0.size(u) - 1
				flg0 = 1
			else:
				if flg1:
					continue
				B += UF1.size(u) - 1
				flg1 = 1
		ans += W * B
	print(ans)
main()


n = int(input())

class UnionFind(object):

	def __init__(self, n):
		self.count = n
		self.uf = [i for i in range(n)]
		self.size = [1] * n

	def find(self, x):
		while x != self.uf[x]:
			self.uf[x] = self.uf[self.uf[x]]
			x = self.uf[x]
		return self.uf[x]

	def union(self, x, y):
		x_root = self.find(x)
		y_root = self.find(y)
		if x_root == y_root:
			return
		if self.size[x_root] < self.size[y_root]:
			(x_root, y_root) = (y_root, x_root)
		self.uf[y_root] = x_root
		self.size[x_root] += self.size[y_root]
		self.size[y_root] = 0
		self.count -= 1
uf0 = UnionFind(n)
uf1 = UnionFind(n)
for i in range(n - 1):
	(a, b, c) = [int(j) for j in input().split(' ')]
	if c == 0:
		uf0.union(a - 1, b - 1)
	else:
		uf1.union(a - 1, b - 1)
res = 0
from collections import *
cnt0 = Counter((uf0.find(k) for k in range(n)))
cnt1 = Counter((uf1.find(k) for k in range(n)))
for (c0, n0) in cnt0.items():
	res += n0 * (n0 - 1)
for (c1, n1) in cnt1.items():
	res += n1 * (n1 - 1)
for i in range(n):
	n0 = cnt0[uf0.find(i)]
	n1 = cnt1[uf1.find(i)]
	res += (n0 - 1) * (n1 - 1)
print(res)


class UnionFindVerSize:

	def __init__(self, N):
		self._parent = [n for n in range(0, N)]
		self._size = [1] * N

	def find_root(self, x):
		if self._parent[x] == x:
			return x
		self._parent[x] = self.find_root(self._parent[x])
		return self._parent[x]

	def unite(self, x, y):
		gx = self.find_root(x)
		gy = self.find_root(y)
		if gx == gy:
			return
		if self._size[gx] < self._size[gy]:
			self._parent[gx] = gy
			self._size[gy] += self._size[gx]
		else:
			self._parent[gy] = gx
			self._size[gx] += self._size[gy]

	def get_size(self, x):
		return self._size[self.find_root(x)]

	def is_same_group(self, x, y):
		return self.find_root(x) == self.find_root(y)

	def calc_group_num(self):
		N = len(self._parent)
		ans = 0
		for i in range(N):
			if self.find_root(i) == i:
				ans += 1
		return ans
import sys
input = sys.stdin.readline
n = int(input())
uf0 = UnionFindVerSize(n)
uf1 = UnionFindVerSize(n)
for i in range(n - 1):
	(x, y, c) = map(int, input().split())
	if c == 0:
		uf0.unite(x - 1, y - 1)
	else:
		uf1.unite(x - 1, y - 1)
data = [0] * n
cnt = [0] * n
for i in range(n):
	root = uf1.find_root(i)
	data[root] += uf0.get_size(i)
	cnt[root] += 1
ans = sum((data[i] * cnt[i] for i in range(n)))
print(ans - n)


from collections import defaultdict

def colour(a, graph, cur, i):
	top = set()
	top.add(i)
	while len(top):
		x = top.pop()
		a[x] = cur
		for y in graph[x]:
			if a[y] == 0:
				top.add(y)

def colour_graph(a, graph, n):
	cur = 0
	for i in range(1, n + 1):
		if a[i] or i not in graph:
			continue
		else:
			cur += 1
			colour(a, graph, cur, i)

def count(col):
	ans = 0
	for el in col:
		if col[el] > 1:
			ans += col[el] * (col[el] - 1)
	return ans
n = int(input())
graph0 = defaultdict(set)
graph1 = defaultdict(set)
vertex0 = set()
a0 = [0] * (n + 1)
a1 = [0] * (n + 1)
for i in range(n - 1):
	(x, y, c) = list(map(int, input().split()))
	if c == 0:
		graph0[x].add(y)
		graph0[y].add(x)
		vertex0.add(x)
		vertex0.add(y)
	else:
		graph1[x].add(y)
		graph1[y].add(x)
colour_graph(a0, graph0, n)
colour_graph(a1, graph1, n)
answer = 0
col0 = defaultdict(int)
col1 = defaultdict(int)
for i in range(n + 1):
	if a0[i]:
		col0[a0[i]] += 1
	if a1[i]:
		col1[a1[i]] += 1
answer += count(col0) + count(col1)
col = defaultdict(int)
for v in vertex0:
	col[a1[v]] += col0[a0[v]] - 1
for el in col:
	if el:
		answer += col[el] * (col1[el] - 1)
print(answer)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(2 * 10 ** 5)
I = lambda : list(map(int, input().split()))
(n,) = I()
r = [[1 for i in range(n)], [1 for i in range(n)]]
p = [[i for i in range(n)], [i for i in range(n)]]

def find(x, c):
	if x != p[c][x]:
		p[c][x] = find(p[c][x], c)
	return p[c][x]

def union(a, b, c):
	x = find(a, c)
	y = find(b, c)
	mm = min(x, y)
	if x != y:
		p[c][y] = p[c][x] = mm
		r[c][mm] += r[c][max(x, y)]
an = 0
for i in range(n - 1):
	(a, b, c) = I()
	union(a - 1, b - 1, c)
vis = [0] * n
cc = []
for i in range(n):
	s0 = r[0][i]
	s1 = r[1][i]
	if p[0][i] == i:
		an += (s0 - 1) * s0
	if p[1][i] == i:
		an += (s1 - 1) * s1
	an += (r[1][find(i, 1)] - 1) * (r[0][find(i, 0)] - 1)
print(an)


class Deque:

	def __init__(self):
		self.buff = [0] * 400000
		self.l = 0
		self.r = 0

	def append(self, x):
		self.buff[self.r] = x
		self.r = self.r + 1

	def popleft(self):
		old_left = self.l
		self.l = self.l + 1
		return self.buff[old_left]

	def __bool__(self):
		return self.l != self.r
q = Deque()

def bfs(source, graph, mark, num, fcount):
	visited = [source]
	mark[source] = True
	q.append(source)
	while q:
		u = q.popleft()
		for (v, c) in g[u]:
			if c == num and (not mark[v]):
				mark[v] = True
				visited.append(v)
				q.append(v)
	if len(visited) > 1:
		for u in visited:
			fcount[u] = len(visited)
n = int(input())
edges = [tuple(map(int, input().split())) for _ in range(0, n - 1)]
g = [[] for _ in range(0, n)]
cnt = [[0 for _ in range(0, n)] for _ in range(0, 2)]
for (u, v, c) in edges:
	g[u - 1].append((v - 1, c))
	g[v - 1].append((u - 1, c))
res = 0
for link in range(0, 2):
	mark = [False] * n
	for u in range(0, n):
		if not mark[u]:
			bfs(u, g, mark, link, cnt[link])
			res += cnt[link][u] * (cnt[link][u] - 1)
for i in range(0, n):
	if cnt[0][i] > 0 and cnt[1][i] > 1:
		res += (cnt[0][i] - 1) * (cnt[1][i] - 1)
print(int(res))


import sys
from collections import deque
from types import GeneratorType
input = lambda : sys.stdin.readline().rstrip()

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
n = int(input())
good_num = [0 for i in range(n + 1)]
mid_num = [0 for i in range(n + 1)]
tree = [[] for i in range(n + 1)]
ans = [0]
for i in range(n - 1):
	(a, b, c) = map(int, input().split())
	tree[a].append((b, c))
	tree[b].append((a, c))
root = 1

@bootstrap
def dfs1(node, pa):
	for (ch, cl) in tree[node]:
		if ch != pa:
			yield dfs1(ch, node)
			if cl:
				mid_num[node] += good_num[ch] + mid_num[ch] + 1
			else:
				good_num[node] += good_num[ch] + 1
	yield 0
dfs1(root, root)

@bootstrap
def dfs2(node, pa, pgood, pmid):
	for (ch, cl) in tree[node]:
		temp = ans[0]
		if ch != pa:
			ans[0] += good_num[ch] + mid_num[ch]
			if cl:
				node_good = pgood + good_num[node]
				node_mid = pmid + mid_num[node] - (mid_num[ch] + good_num[ch])
				ans[0] += node_good + node_mid
				yield dfs2(ch, node, 0, node_mid + node_good)
			else:
				node_good = pgood + (good_num[node] - good_num[ch])
				ans[0] += node_good
				yield dfs2(ch, node, node_good, 0)
	yield 0
ans[0] = good_num[root] + mid_num[root]
dfs2(root, root, 0, 0)
print(ans[0])


class UnionFind:

	def __init__(self, n):
		self.n = n
		self.root = [-1] * (n + 1)
		self.rnk = [0] * (n + 1)

	def Find_Root(self, x):
		if self.root[x] < 0:
			return x
		else:
			self.root[x] = self.Find_Root(self.root[x])
			return self.root[x]

	def Unite(self, x, y):
		x = self.Find_Root(x)
		y = self.Find_Root(y)
		if x == y:
			return
		elif self.rnk[x] > self.rnk[y]:
			self.root[x] += self.root[y]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			self.root[x] = y
			if self.rnk[x] == self.rnk[y]:
				self.rnk[y] += 1

	def isSameGroup(self, x, y):
		return self.Find_Root(x) == self.Find_Root(y)

	def Count(self, x):
		return -self.root[self.Find_Root(x)]
import sys
input = sys.stdin.readline
N = int(input())
uni0 = UnionFind(N)
uni1 = UnionFind(N)
for _ in range(N - 1):
	(a, b, c) = map(int, input().split())
	if c == 0:
		uni0.Unite(a - 1, b - 1)
	else:
		uni1.Unite(a - 1, b - 1)
g0 = {}
g1 = {}
for i in range(N):
	if uni0.Count(i) != 1:
		r = uni0.Find_Root(i)
		if not r in g0.keys():
			g0[r] = [i]
		else:
			g0[r].append(i)
	if uni1.Count(i) != 1:
		r = uni1.Find_Root(i)
		if not r in g1.keys():
			g1[r] = [i]
		else:
			g1[r].append(i)
ans = 0
for v_list in g1.values():
	c = 0
	for n in v_list:
		if uni0.Count(n) == 1:
			c += 1
	l = len(v_list)
	ans += c * (l - 1)
for v_list in g0.values():
	c = 0
	for n in v_list:
		if uni1.Count(n) != 1:
			r = uni1.Find_Root(n)
			c += len(g1[r]) - 1
	c += len(v_list) - 1
	ans += len(v_list) * c
print(ans)