#2291. 【模板】字典树 3

【模板】字典树 3

题目描述

Macesuted 会给你一个由 nn 个点组成的树,每条边都有边权。 他将树上两点间距离 disi,j(1i,jn)dis_{i,j}(1\le i,j\le n) 定义为 i,ji,j 两间点简单路径上所有边权的异或和。

但 Macesuted 并不想问你树上任意两点间距离最大是多少,这对于你来说太简单了。他现在想要知道树上有多少点对 (i,j)(i,j)满足 iji\le jdisi,jkdis_{i,j}\ge k

输入格式

第一行两个整数 n,kn,k,含义如题意所述。
接着 n1n-1 行,每行三个整数 x,y,zx,y,z,表示点 xx 和点 yy 之间有一条长为 zz 的无向边。

输出格式

一行一个整数,表示满足条件的点对数量。

6 3
1 2 1
1 3 5
2 4 7
2 5 3
3 6 6

11

样例说明 1

下面列出任意点对间距离(竖 iijjiji\le j):

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

根据图表可发现满足条件的点对数量为 1111

数据规模与约定

数据有梯度。

对于 50%50\% 的数据,n104n\le10^4
对于 100%100\% 的数据,1<x,yn1061< x,y\le n\le10^61z,k1081\le z,k\le 10^8