dDisguised | Logout
HOME TOP CATALOG CONTESTS GYM PROBLEMSET GROUPS RATING EDU API CALENDAR HELP
PROBLEMS SUBMIT CODE MY SUBMISSIONS STATUS HACKS STANDINGS CUSTOM INVOCATION
Codeforces Round 1103 (Div. 3)
G. Criterion in Burlandia Finished
time limit per test: 3 seconds Practice
memory limit per test: 512 megabytes
Regions in Burlandia form a graph with n vertices and n − 1 edges, and there is exactly one
path between any two vertices. Formally, the regions form a tree.
→ Virtual participation
Each region has a friendliness value ai .
Virtual contest is a way to take part in past contest,
as close as possible to participation on time. It is
There are q queries. In each query, a pair of friends located in different regions is given. They supported only ICPC mode for virtual contests. If
want to know how many subsegments of the path between these regions are hospitable. you've seen these problems, a virtual contest is not
for you - solve these problems in the archive. If you
just want to solve some problem from a contest, a
It is known that in Burlandia there are two criteria for evaluating relationships — XOR and sum. virtual contest is not for you - solve this problem in
A subsegment of the path, containing some vertices lying on the path from region x to region the archive. Never use someone else's code, read
the tutorials or communicate with other person
y, is called hospitable if it is non-empty and the sum of friendliness values on this subsegment during a virtual contest.
does not exceed their XOR.
Start virtual contest
More formally, for each query you are given two vertices x and y (x ≠ y). Consider the
shortest path from vertex x to vertex y in the tree. Let the vertices v1 , v2 , … , vk form this
path, where v1 = x, vk = y . You need to find the number of subsegments of this path for → Clone Contest to Mashup
which the following condition holds:
You can clone this contest to a mashup.
av ⊕ av ⊕ … ⊕ av ≥ (av + av + … + av ),
l l+1 r l l+1 r
Clone Contest
where 1 ≤ l ≤ r ≤ k — the boundaries of the subsegment of vertices on the path from x to
y.
→ Submit?
Input
Each test consists of multiple test cases. The first line contains a single integer t ( Language: Python 3.13.2
4
) — the number of test cases. Then the descriptions of the test cases follow. Almost always, if you send a solution on
1 ≤ t ≤ 10
PyPy, it works much faster
5 Choose
The first line of each test case contains integers n (2 ≤ n ≤ 10 ) — the number of vertices in Choose File No file chosen
file:
5
the tree, and q (1 ≤ q ≤ 10 ) — the number of queries.
The second line contains an array of n non-negative integers — the friendliness values of the
20
regions (0 ≤ ai < 2 ).
The next n − 1 lines describe the edges of the tree: each line contains integers u, v (
1 ≤ u, v ≤ n) — an edge.
Then q lines follow describing the queries. Each query is given by integers x, y (1 ≤ x, y ≤ n ,
x ≠ y) — the vertices that define the path for which you need to count the number of
hospitable subsegments.
Submit
5
It is guaranteed that the sum of n and the sum of q over all test cases do not exceed 10 , and
that the edges indeed form a tree.
→ Problem tags
Output
For each query output an answer on a separate line. brute force data structures implementation
No tag edit access
Example
input Copy
3
4 3
0 0 4 1
1 2
1 3
1 4
1 4
2 3
2 4
4 3
0 4 1 2
1 3
1 4
2 4
1 2
2 3
2 4
4 3
3 2 4 4
1 2
2 4
3 4
1 2
1 3
2 3
output Copy
3
6
6
6
10
3
2
5
4
Note
For clarity, consider the third query from the third sample.
The path from vertex 2 to vertex 3 consists of vertices 2, 4, 3.
The subsegment [2; 3] does not satisfy the condition, since the XOR on it is
a4 ⊕ a3 = 4 ⊕ 4 = 0 , while the sum is a4 + a3 = 4 + 4 = 8 .
The subsegment [1; 3] does not satisfy the condition, since the XOR on it is
a2 ⊕ a4 ⊕ a3 = 2 ⊕ 4 ⊕ 4 = 2 , while the sum is a2 + a4 + a3 = 2 + 4 + 4 = 10.
It can be shown that all other 4 subsegments satisfy the condition.
For each query, output the answer in a separate line.
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Jun/13/2026 03:03:24UTC+6 (g1).
Desktop version, switch to mobile version.
Privacy Policy | Terms and Conditions
Supported by