F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist

C/C++/Java Exams
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
DIY | Web-DIY beta
Register new ID

# Ants

Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 327680/327680 K (Java/Others)
Total Submission(s): 1577    Accepted Submission(s): 400

Problem Description
There are some apple trees in a farm. An apple tree can be described as a connected graph which has n nodes and n-1 edges. The apples are the nodes and the branches are the edges. Every edge is assigned a value denoting the length of the branch.
Now in the farm come a lot of ants, which are going to enjoy the delicious apples. The ants climb the tree one by one. Every ant would choose a node as the starting node and another node as the ending node, then it would crawl alone the unique path from the starting node to the ending node. The distance between two nodes is defined as the XOR sum of lengths of all the edges in the unique path between them. Every ant wants to crawl along such a path which the distance is as large as possible. But two ants cannot crawl from the same starting node to the same ending node. You should calculate the distance which the k-th ant crawled.
Note that the starting node and the ending node cannot be the same for an ant.

Input
The input consists of several test case.
For each test case, the first line contain an integer n denoting the number of nodes.
The next n-1 lines each contains three integers x,y,z, denoting that there exists an edge between node x and node y and its length is z. The nodes are numbered from 1 to n.
The next line contain a integer m denoting the number of queries.
In the next m lines, each line contains an integer k denoting that you need to calculate the distance of the k-th ant.
The input ends with n = 0.
(1 <= n, m <= 100000, 1 <= x, y <= n, 0 <= z <= 1018, 1 <= k <= 200000)

Output
For each query, output the answer. If such path does not exist, just output -1.

Sample Input
3
1 2 2
3 2 3
3
1
2
5
5
1 3 7
2 1 3
4 3 6
5 3 1
3
1
8
1000
0


Sample Output
3
3
1
7
6
-1

Hint

In the first test case, the first ant may crawl from node 2 to node 3, and the second ant may crawl from node 3 to node 2, and the 5-th ant may crawl from node 1 to node 3.
The distance of the 5-th ant can be calculated by 2 xor 3 = 1.

Source

Statistic | Submit | Discuss | Note
 Home | Top Hangzhou Dianzi University Online Judge 3.0 Copyright © 2005-2024 HDU ACM Team. All Rights Reserved. Designer & Developer : Wang Rongtao LinLe GaoJie GanLu Total 0.000000(s) query 1, Server time : 2024-08-14 18:28:54, Gzip enabled Administration