#2291. 【模板】字典树 3
【模板】字典树 3
题目描述
Macesuted 会给你一个由 个点组成的树,每条边都有边权。 他将树上两点间距离 定义为 两间点简单路径上所有边权的异或和。
但 Macesuted 并不想问你树上任意两点间距离最大是多少,这对于你来说太简单了。他现在想要知道树上有多少点对 满足 且 。
输入格式
第一行两个整数 ,含义如题意所述。
接着 行,每行三个整数 ,表示点 和点 之间有一条长为 的无向边。
输出格式
一行一个整数,表示满足条件的点对数量。
6 3
1 2 1
1 3 5
2 4 7
2 5 3
3 6 6
11
样例说明 1
下面列出任意点对间距离(竖 横 ,):
1 | 2 | 3 | 4 | 5 | 6 | |
---|---|---|---|---|---|---|
1 | 0 | 1 | 5 | 6 | 2 | 3 |
2 | - | 0 | 4 | 7 | 3 | 2 |
3 | - | 0 | 3 | 7 | 6 | |
4 | - | 0 | 4 | 5 | ||
5 | - | 0 | 1 | |||
6 | - | 0 |
根据图表可发现满足条件的点对数量为 。
数据规模与约定
数据有梯度。
对于 的数据,。
对于 的数据,,。