Description

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$.

Input Format

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:

#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){ //你需要传入三个参数，分别表示点权，一条边的两个端点 
		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){
		//直接输入 
	}else{
		int n;
		scanf("%d %d",&Generate::seed,&n);//输入种子和n 
		Generate::n=n;//记得赋值 
		Generate::RS(a,u,v); //开始工作 
	}
	return 0;
}

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

Output Format

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

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

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

19

2
10086001 100000

26892182890608

Hint

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$	$2$	/	/
2	4		$3$
3	10		$\leq 6$	$\leq 3$
4	5		$\leq 10^6$	/	A
5	15		$\leq 50$		/
6	5		$\leq 5\times 10^3$	$\leq 100$	B
7	10		$\leq 10^5$
8				/	C
9				$\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]

ree 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