小K的疑惑

[编程题]小K的疑惑

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

众所周知，小K是一只连NOIP2018初赛都没有过的蒟蒻，所以小K很擅长dfs序+分块树，但是本题与dfs序+分块树无关。

小K现在心态爆炸了，因为小K被一道简单的数据结构题给卡住了，希望请你来解决它，但是小K又不想太麻烦你，于是将题面进行了简化~~（其实是出题人懒得写题面了233333）~~：

Bob有𝑁个点的树，每条边的长度有一个边权，现在定义𝑑𝑖𝑠(𝑖,𝑗)代表第𝑖个点到第𝑗个点的距离模2之后的结果。问有多少(𝑖,𝑗,𝑘)满足，𝑑𝑖𝑠(𝑖,𝑗) = 𝑑𝑖𝑠(𝑗,𝑘) = 𝑑𝑖𝑠(𝑖,𝑘)。

输入描述:

第一行一个整数𝑁代表点的数量。

接下来𝑁 − 1行每行三个数𝑠,𝑒,𝑑代表有一条在𝑠,𝑒之间长度为𝑑的边。

输出描述:

一行一个整数代表有多少对(𝑖,𝑗,𝑘)满足条件。

示例1

输入

3
1 2 3
1 3 4

输出

备注:

对于100%的数据，1 ≤ 𝑁 ≤ 10000，0 ≤ 𝑑 ≤ 233。

算法知识视频讲解

东溪看水

发表于 2020-08-06 11:57:37

题目给定一个有 𝑁 个点的树，每条边的长度有一个边权，现在定义 𝑑𝑖𝑠(𝑖,𝑗) 代表第 𝑖 个点到第 𝑗 个点的距离模 2 之后的结果。问有多少 (𝑖,𝑗,𝑘) 满足，𝑑𝑖𝑠(𝑖,𝑗) = 𝑑𝑖𝑠(𝑗,𝑘) = 𝑑𝑖𝑠(𝑖,𝑘)。解题思路可展开全文

CallmeChallenger

发表于 2020-08-05 00:40:02

题目链接：https://ac.nowcoder.com/acm/contest/6760/A题意：树上找出满足dis(i,j)=dis(j,k)=dis(i,k)的三元组的个数。且dis(i,j)的定义是i到j的距离对2取模题解：我们可以将两个点之间的距离，全部转换成到根的距离。我的做法就是再找一展开全文