Truy vấn trên cây - MarisaOJ: Marisa Online Judge

Truy vấn trên cây

Time limit: 1000 ms
Memory limit: 256 MB
Cho cây $n$ đỉnh, mỗi đỉnh mang giá trị $1$ hoặc $-1$. Cho $q$ truy vấn $(u,v)$, đếm số lượng đỉnh $t$ nằm trên đường đi đơn từ $u$ đến $v$ mà tổng các đỉnh trên đường đi đơn từ $u$ đến $t$ có tổng là dương. ### Input - Dòng đầu tiên gồm hai số nguyên $n,q$. - Dòng thứ hai gồm $n$ số nguyên là giá trị của các đỉnh từ $1$ đến $n$. - $n - 1$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $u,v$ là một cạnh của cây. - $q$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $u,v$. ### Output - Với mỗi truy vấn in ra một số nguyên là đáp án. ### Điều kiện - $1 \le n,q \le 10^5$. - $1 \le u,v \le n$. ### Ví dụ Input: ``` 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: ``` 5 1 0 2 2 ```