5416：CRB and Tree

题目描述

CRB has a tree, whose vertices are labeled by 1, 2, …, $N$. They are connected by $N$ – 1 edges. Each edge has a weight.
For any two vertices $u$ and $v$(possibly equal), $f(u, v)$ is xor(exclusive-or) sum of weights of all edges on the path from $u$ to $v$.
CRB’s task is for given $s$, to calculate the number of unordered pairs $(u, v)$ such that $f(u, v)\ =\ s$. Can you help him?

输入解释

There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:
The first line contains an integer $N$ denoting the number of vertices.
Each of the next $N$ - 1 lines contains three space separated integers $a$, $b$ and $c$ denoting an edge between $a$ and $b$, whose weight is $c$.
The next line contains an integer $Q$ denoting the number of queries.
Each of the next $Q$ lines contains a single integer $s$.
1 ≤ $T$ ≤ 25
1 ≤ $N$ ≤ $10^{5}$
1 ≤ $Q$ ≤ 10
1 ≤ $a$, $b$ ≤ $N$
0 ≤ $c$, $s$ ≤ $10^{5}$
It is guaranteed that given edges form a tree.

输出解释

For each query, output one line containing the answer.

输入样例

输出样例

1
1
0

提示

For the first query, (2, 3) is the only pair that f(u, v) = 2.
For the second query, (1, 3) is the only one.
For the third query, there are no pair (u, v) such that f(u, v) = 4.

来自杭电HDUOJ的附加信息

Author	KUT（DPRK）
Recommend	wange2014

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 2015 Multi-University Training Contest 10

源链接： HDU-5416

最后修改于 2020-10-25T23:22:29+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
8000/4000MS(Java/Others)	65536/65536K(Java/Others)