该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

树上异或路径

题目背景

考古队在一片遗迹里发现了一张古老的地图：若干座石塔之间由通道相连，任意两座石塔之间恰好存在唯一一条通路。每条通道上都刻着一个数字。探险家不仅想知道“异或值最大”的那一对石塔，还想知道有多少对石塔的路径异或值恰好等于藏宝图上的数字 $X$。

题目描述

给定一棵 $n$ 个结点的树，结点编号 $1$ 到 $n$，第 $i$ 条边有非负整数权值 $w_i$。再给定一个非负整数 $X$。

对任意两个结点 $u, v$，定义它们的路径异或和为：从 $u$ 到 $v$ 的唯一简单路径上所有边权的按位异或结果。

请你完成两件事：

1. 求出所有满足 $1 \le u < v \le n$ 的点对 $(u,v)$ 中，路径异或和的最大值；
2. 求出所有满足 $1 \le u < v \le n$ 的点对中，路径异或和恰好等于 $X$ 的点对个数。

按位异或（记为 $\oplus$）指把两个整数写成二进制后逐位比较，相同为 $0$，不同为 $1$。例如 $5 \oplus 3 = 6$。

输入格式

从标准输入读入数据。

第一行两个整数 $n, X$。

接下来 $n-1$ 行，每行三个整数 $u_i, v_i, w_i$，表示结点 $u_i$ 与 $v_i$ 之间有一条权值为 $w_i$ 的边，保证给出的图是一棵树。

输出格式

输出到标准输出。

输出一行两个整数，用一个空格隔开：路径异或和的最大值，以及路径异或和恰好等于 $X$ 的点对个数。

样例 1 输入

3 2
1 2 5
2 3 7

样例 1 输出

7 1

样例 1 解释

三条路径的异或和分别是：$(1,2)$ 为 $5$，$(1,3)$ 为 $5 \oplus 7 = 2$，$(2,3)$ 为 $7$。最大值是 $7$；恰好等于 $X=2$ 的点对只有 $(1,3)$ 一对，所以第二个数是 $1$。

样例 2 输入

4 0
1 2 0
2 3 1
3 4 1

样例 2 输出

1 3

样例 2 解释

以 $1$ 为根，根到各点的异或值为 $0, 0, 1, 0$。两两异或的结果中最大的是 $1$（例如 $(1,3)$）；异或值为 $0$ 的点对有 $(1,2),(1,4),(2,4)$，共 $3$ 对。

特殊性质

• 特殊性质 A：所有边权都不超过 $1$，即 $w_i \in \{0,1\}$。此时任意路径的异或和只能是 $0$ 或 $1$，第一问的答案不超过 $1$，可以直接统计“异或和为 $0$ 与 $1$ 的点对是否存在”，计数部分也可以按“同一取值内部的点对数”直接算。
• 特殊性质 B：树是一条链，即对每个 $1 \le i < n$ 都有一条连接 $i$ 与 $i+1$ 的边，且不存在其它边。此时问题退化成序列上的“前缀异或”问题。
• 特殊性质 C：$X = 0$。此时第二问变成“统计异或和恰为 $0$ 的点对数”，也就是统计根到各点的异或值里有多少对相等。

数据范围与子任务

对全部测试数据，保证 $2 \le n \le 2 \times 10^5$，$0 \le w_i \le 10^9$，$0 \le X \le 10^9$。

部分分提示

• 子任务 1：$n \le 2000$，直接枚举所有点对，并用一次 DFS 求出根到每个点的异或值后 $O(1)$ 计算路径异或和，总共 $O(n^2)$。
• 子任务 2：满足 A 时异或值只有 $0$ 和 $1$ 两种，第一问只要看是否两种取值都出现，第二问直接统计取值分布；满足 C 时第二问只需统计相同取值之间能组成的点对数（若某个取值出现 $c$ 次，就有 $\frac{c(c-1)}{2}$ 对）。
• 子任务 3：树是链，可以用前缀异或把它变成“一串数字两两异或”的问题，仍然可以用 01-Trie 求最大异或对、用排序 + 双指针/二分统计等于 $X$ 的对数。
• 子任务 4：先求根到每个点的异或值 $d_i$（路径异或和就是 $d_u \oplus d_v$）。第一问用 01-Trie 求“最大异或对”；第二问把 $d$ 排序，对每个 $d_i$ 二分统计 $d_i \oplus X$ 的出现次数（只统计下标更大的，避免重复）。注意答案要用 $64$ 位整数。

提交说明

本题使用标准输入输出。程序应从标准输入读入数据，并将答案输出到标准输出。