P7246 Gesture Password.

  Being asked to unlock someone else’s phone in front of everyone is a very terrifying thing.   —Especially when the password is about yourself. ---   Surrounded by a dense crowd of classmates around the podium, Xiaohuimao felt it was really hard. As the class monitor, A Ling was called to a meeting, and her phone containing the monthly exam ranking table was handed to Tianyi for safekeeping. But as expected, the news leaked out. Now the “hungry wolves” of Class 1 who coveted the score testdata unanimously demanded that Tianyi unlock the phone……   “I really don’t know the password!” she stalled, while in her heart she had already guessed the answer to the gesture password.   In the end, she hesitantly yet confidently drew the letter “Y”, and it unlocked successfully. What did it mean? First, rule out the initial letter of “Yi”.   At this moment, of course people started to egg it on!   “If you know, you know\~” “Don’t ask, asking means [XX is justice!](https://www.bilibili.com/video/BV1z741137vQ)”…… # Background   Being asked to unlock someone else’s phone in front of everyone is a very terrifying thing.   —Especially when the password is about yourself. ---   Surrounded by a dense crowd of classmates around the podium, Xiaohuimao felt it was really hard. As the class monitor, A Ling was called to a meeting, and her phone containing the monthly exam ranking table was handed to Tianyi for safekeeping. But as expected, the news leaked out. Now the “hungry wolves” of Class 1 who coveted the score testdata unanimously demanded that Tianyi unlock the phone……   “I really don’t know the password!” she stalled, while in her heart she had already guessed the answer to the gesture password.   In the end, she hesitantly yet confidently drew the letter “Y”, and it unlocked successfully. What did it mean? First, rule out the initial letter of “Yi”.   At this moment, of course people started to egg it on!   “If you know, you know\~” “Don’t ask, asking means [XX is justice!](https://www.bilibili.com/video/BV1z741137vQ)”……

Miss Yuezheng’s phone is very advanced, so her gesture password is also very fancy. Specifically, there is now a tree with $n$ nodes. For two nodes $u,v$, the gesture can move from one node ($u$ or $v$) to the other node ($v$ or $u$) if and only if $(u,v)$ is a tree edge. Even stranger, this gesture password does not restrict you to drawing only once, but each drawn path must be a simple path on the tree. Now A Ling tells Tianyi, for her password, how many times each node is passed by the gesture (being the start or end of a gesture also counts as being passed once). The $i$-th node is passed $a_i$ times. Then, what is the minimum number of strokes Tianyi needs to draw to unlock the password? ---- #### Simplified statement There is a tree with weights on nodes. Define one operation as choosing a simple path on the tree and decreasing the weights of all nodes on this simple path by $1$. Ask for the minimum number of operations needed so that all node weights on the tree become **exactly** $0$.

The first line contains an integer $op$, indicating the type of input method. If $op=1$: The second line contains a positive integer $n$, indicating the number of nodes. The third line contains $n$ non-negative integers $a_1,a_2,\cdots,a_n$, indicating the weight of each node. The next $n-1$ lines each contain two positive integers $u,v$, indicating a tree edge connecting node $u$ and node $v$. If $op=2$: We will provide an input template: ```cpp #include int a[3000005], u[3000005],v[3000005]; namespace Generate{ int n,seed; static const int mod=1e9; int Rand(int x){ seed=(1ll*seed*0x66CCF+19260817ll)%x+1; seed=(1ll*seed*0x77CCF+20060428ll)%x+1; seed=(1ll*seed*0x88CCF+12345678ll)%x+1; seed=(1ll*seed*0x33CCCCFF+10086001ll)%x+1; return seed; } void RS(int* a, int* u, int* v){ //你需要传入三个参数，分别表示点权，一条边的两个端点 int cnt=0; for(int i=1;i

Output one integer in one line, indicating the minimum number of operations.

#### Explanation of Sample 2 The given tree shape is as follows. The numbers in parentheses represent the node weights.  One optimal sequence of operations is $(3,4)\times2,(4,5),(4,4)\times4,(5,5)\times4,(4,7),(7,8),(6,7)\times6$. Here, $(u,v)$ means performing one operation on the simple path from $u$ to $v$. ------------ #### Constraints and Notes **This problem uses bundled testdata.** For $100\%$ of the data, $op\in\{1,2\},1\le seed\le 10^9,1\le n\le 3\times 10^6,0\le a_i\le10^9,1\le u,v\le n$, and it is guaranteed that $u\ne v$. | Subtask | Score | $op$ | $n$ | $a_i$ | Special Property | | :-----: | :---: | :--------: | :----------------------: | :-------------: | :--------------: | | 1 | 1 | $1$ | $2$ | / | / | | 2 | 4 | $1$ | $3$ | / | / | | 3 | 10 | $1$ | $\leq 6$ | $\leq 3$ | / | | 4 | 5 | $1$ | $\leq 10^6$ | / | A | | 5 | 15 | $1$ | $\leq 50$ | / | / | | 6 | 5 | $1$ | $\leq 5\times 10^3$ | $\leq 100$ | B | | 7 | 10 | $1$ | $\leq 10^5$ | $\leq 100$ | B | | 8 | 10 | $1$ | $\leq 10^5$ | / | C | | 9 | 10 | $1$ | $\leq 10^5$ | $\leq 100$ | / | | 10 | 30 | / | / | / | / | - Special restriction A: For the $i$-th edge $(u,v)$, it is guaranteed that $u=i,v=i+1$. - Special restriction B: The input edges form a full binary tree. - Special restriction C: For all $1\le i\le n$, $a_i=1$. ------------ #### Notes The time limit for Subtask 10 is 2S. For data with $op=2$, the input template is only used to reduce input size. The standard solution does not depend on this generation method. [2024.7.2 Supplement] @[Edward1002001](https://www.luogu.com.cn/user/151415) pointed out that the tree generated for Subtask 10 is not random. (Because when generating the parent of node $2$, the final `seed` will definitely become $1$, and after that the random sequence is completely the same.) This does not affect the correctness of the testdata, but it reduces the strength of the data. We apologize for this. Since there have been many submissions for this problem, we will not modify the statement or the testdata. Translated by ChatGPT 5