Problem Background

Under the watchful eyes of everyone, being asked to unlock someone else's phone is a terrifying experience.

—Especially when the password is about oneself.

Surrounded by a crowd of classmates, Little Gray felt really stuck. As the class monitor, A Ling was called to a meeting, and the phone containing the monthly exam rankings was entrusted to Tian Yi for safekeeping. But the news leaked as expected, and now the entire class, like a pack of hungry wolves eyeing the score data, unanimously demanded Tian Yi to unlock the phone...

"I really don't know the password!" Procrastinating, Tian Yi already guessed the answer to the gesture password.

Finally, tentatively and confidently, a letter "Y" was drawn, and the unlock was successful. What does it mean? First, eliminate the initial letter of "Yi".

At this moment, there must be some heckling!

"Those who understand, understand~" "Don't ask, ask is XX is justice!"...

Problem Description

Miss Yue Zheng's phone is very advanced, so her gesture password is also quite fancy.

Specifically, there is a tree with $n$ nodes. For two nodes $u, v$, the gesture can only be drawn from one node ($u$ or $v$) to another node ($v$ or $u$) if $(u, v)$ is a tree edge. What's more peculiar is that this gesture password does not limit to just one stroke, but each stroke must be a simple path on the tree.

Now, A Ling has told Tian Yi the number of times each node is touched by the gesture (including starting and ending points), where the $i$-th node is touched $a_i$ times. How many times does Tian Yi need to draw at least to unlock the password?

Simplified Problem Statement

There is a tree with node weights. Define an operation as selecting a simple path on the tree and subtracting 1 from the weights of all nodes on this path. How many operations are needed at least to make the weights of all nodes exactly become 0?

Input Output Format

Input Format

The first line contains an integer $op$, indicating the type of data input.

If $op=1$:

The second line contains a positive integer $n$, the number of nodes.

The third line contains $n$ non-negative integers $a_1, a_2, \cdots, a_n$, the weights of each node.

The next $n-1$ lines, each containing two positive integers $u, v$, represent a tree edge connecting node $u$ and node $v$.

If $op=2$:

We will provide an input template:

#include <cstdio>
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){ //You need to pass in three parameters, representing the node weights and the two endpoints of an edge 
        int cnt=0;
        for(int i=1;i<=n;i++)a[i]=Rand(mod); 
        for(int i=2;i<=n;i++){
            int fa=Rand(i-1);
            cnt++;
            u[cnt]=fa,v[cnt]=i;
        }
    }
};
int main () {
    int op;
    scanf("%d",&op);
    if(op==1){
        //Direct input 
    }else{
        int n;
        scanf("%d %d",&Generate::seed,&n);//Input seed and n 
        Generate::n=n;//Remember to assign the value 
        Generate::RS(a,u,v); //Start working 
    }
    return 0;
}

The second line contains two integers $seed$ and $n$, the generator's seed and the number of nodes.

Output Format

A single line containing an integer, the minimum number of operations.

Sample Input and Output

Sample Input #1

1
4
1 2 1 2
1 2
2 3
2 4

Sample Output #1

2

Sample Input #2

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

Sample Output #2

19

Sample Input #3

2
10086001 100000

Sample Output #3

26892182890608

Notes/Hints

Sample Explanation 2

The given tree structure is as follows, with the numbers in parentheses indicating the node weights.

An optimal operation scheme is $(3,4)\times2,(4,5),(4,4)\times4,(5,5)\times4,(4,7),(7,8),(6,7)\times6$. Here, $(u,v)$ represents an operation on the simple path from $u$ to $v$.

Data Size and Constraints

This problem uses bundled testing.

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 $u\ne v$ are guaranteed.

• 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 $\forall 1\le i\le n$, $a_i=1$.

Hint

Subtask 10 has a time limit of 2 seconds.

For $op=2$ data, the input template is only used to reduce the input size, and the standard solution does not rely on this data generation method.

[2024.7.2 Update] @Edward1002001 pointed out that the tree shape generated by the data generator in Subtask 10 lacks randomness. (Because when generating the father of $2$, the final seed will definitely become $1$, and the subsequent random sequence will be exactly the same.) This does not affect the correctness of the data but reduces the strength of the data. We apologize for this. Given the high number of submissions for this problem, no changes to the problem statement or data will be made.

见题面 Input 部分

见题面 Output 部分