Queries on tree 3 - MarisaOJ: Marisa Online Judge

Given a tree with

n

$n$ nodes, each node has a value of

1

$1$ or

- 1

$-1$ . For

q

$q$ queries

(u, v)

$(u, v)$ , count the number of nodes

t

$t$ on the simple path from

u

$u$ to

v

$v$ such that the sum of node values on the simple path from

u

$u$ to

t

$t$ is positive. ### Input - The first line contains two integers

n

$n$ and

q

$q$ . - The second line contains

n

$n$ integers representing the values of the nodes from

1

$1$ to

n

$n$ . - The next

n - 1

$n - 1$ lines each contain two integers

u, v

$u, v$ representing an edge of the tree. - The next

q

$q$ lines each contain two integers

u, v

$u, v$ representing a query. ### Output - For each query, print a single integer as the answer. ### Constraints -

1 \leq n, q \leq 10^{5}

$1 \le n,q \le 10^5$ . -

1 \leq u, v \leq n

$1 \le u,v \le n$ . ### Example Input:

85 - 1111 - 111 - 1155636454748123822172764

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

Output:

51022

$5 1 0 2 2$

Topic

Tree

Rating

1900

Solution (0)

Solution