Selling potion - MarisaOJ: Marisa Online Judge

Selling potion

Time limit: 1000 ms
Memory limit: 256 MB
Marisa, after brewing potions, proceeds to sell them. The Human Village can be visualized as a tree of $n$ vertices, where each vertex represents a house. House $i$ has a maximum purchasing limit of $A_i$ bottles from Marisa. Over the next $k$ days, Marisa plans to transport $c_i$ bottles and sell them along the simple path connecting houses $u_i$ and $v_i$. What is the maximum number of potion bottles she can sell in $k$ days? ### Input - The first line contains two integers $n,k$. - The second line contains $n$ integers $A_i$. - The next $n - 1$ lines, each line contains two integers $u,v$, there is an edge between $u$ and $v$. - The next $k$ lines, each line contains three integers $u_i,v_i,c_i$. ### Output - Print the maximum number of potion bottles Marisa can sell. ### Constraints - $1 \le n, k \le 10^4$. - $0 \le A_i \le 10^5$. - $1 \le u, v \le n$. - $1 \le c_i \le 10^5$. ### Example Input: ``` 4 2 0 1 2 2 1 4 2 4 3 4 1 2 2 1 3 3 ``` Output: ``` 5 ```
Topic
Tree
Data structure
Flow
Rating 2000
Solution (0) Solution