+ محدودیت زمان: ۵ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ---------- We have a country with $n$ cities. The cities in this country are connected by $n - 1$ two-way roads. We know that from each city, we can reach any other city by traversing some roads, meaning the structure of this country is a tree. The cities are numbered from $1$ to $n$. We know the population of city $i$ is $w_i$. The \textit{difference} between two cities is defined as the XOR of the populations of the cities along the path between the two cities (including the start and end). The \textit{value} of the country is the sum of the differences between every pair of distinct cities. Calculating the initial value of the country is not a hard task for the mayor. Therefore, we ask you to design a dynamic system. You will receive $q$ queries. In each query, the population of city $v$ changes to $x$. We want you to write a program that calculates the initial value of the country and the value of the country after each change. # ورودی The first line of input contains an integer $n$, representing the number of cities in the country. $$1 \leq n\leq 10^5$$ The second line contains $n$ integers $w_1, w_2, \dots, w_n$, representing the initial population of each city. $$0 \leq w_i \leq 10^8$$ Each of the next $n - 1$ lines contain two integers $u$ and $v$, representing a road between cities $u$ and $v$ in the country. $$1 \leq u, v\leq n$$ The following line contains an integer $q$, representing the number of queries. $$1 \leq q \leq 10^5$$ The next $q$ lines each contain two integers $v$ and $x$, representing an operation that changes the population $w_v$ of city $v$ to $x$. It is guarantied that the roads form a tree. $$0 \leq x \leq 10^8$$ $$1 \leq v\leq n$$ # خروجی The output consists of $q + 1$ lines, where each line contains an integer representing the current value of the country. # مثال‌ها ## ورودی نمونه ۱ ``` 5 10 11 8 3 17 1 2 1 3 2 4 2 5 3 4 16 1 5 5 5 ```` ## خروجی نمونه ۱ ``` 123 157 202 170 ````

حل سؤال در بانک سؤالات