BdOI 2013 National Problem 7

Discuss everything related to IOI here. For more general or advanced topics use CS forum.

Moderators: bristy1588, Labib

User avatar
Posts: 92
Joined: Sun Jun 19, 2011 10:31 am

BdOI 2013 National Problem 7

Unread post by bristy1588 » Wed Jan 15, 2014 12:35 pm

Xorer are ancient race. They were very advance in their time. Their kingdom consisted of $N$ cities numbered from $1$ to $N$. Each city was connected with each other by a unique path of one or more roads. There was no cycle among the cities, means you cannot go from one city to another in more than one way without going to a city twice. We can say their road system can be modeled as a Tree of graph theory where each city is a node and each road is an edge connecting two cities. So there are $N-1$ roads. They had to give some tax for crossing each road. But for their strange economical system, whenever they cross 2 or more roads, their total tax needed was the Bitwise XOR (^ operator in C/C++) of taxes of all the roads.

Now we got a map of their road system. We want to know that, for some pair of cities U and V, how much tax one had to pay for going to city U to V in the cheapest path (Cheapest in terms of taxes).

First line of the input is the test case number $T (T <= 5)$. Then T test cases follow. Each case
starts with two integers $ N (1 <= N <= 20000) $ and $Q (1 <= Q <= 20000) $. $N$ is the number of
city of the road system. $Q$ is the number of pair of cities for which you need to calculate the
tax. In next $N-1$ lines, there will be $3$ integer numbers $U, V$ and $W (1 <= U, V <= N$ and $0 <= W
<= 1000000)$. This means there was a road from city $ U$ to city $V $ and if anybody wants to go
to only from $U$ to $ V$ or $V$ to $ U$, he/she has to give $W$ tax. Or if they are going to any other
cities and they cross this road, the cost needed will be XORed with W. Then Q lines follow ; in
each line there will be$ 2$ integer numbers $U$ and $V$. $ (1 <= U, V <= N)$

For each test case first print $"Case$ $C:"$ where $C$ is the test case number. Then $Q$ lines follow;
each line consists of a single number, minimum tax needed for going from city $U$ to city $V$ in
cheapest path.


Code: Select all

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

Code: Select all

Case 1:
Case 2:
Bristy Sikder

Post Reply