# 2024/5/25 APCS 第五場模擬賽 題解
## 磁鐵 (Magnet)

> 出題者：ysh
> 難度：p1
> 考點：implemention

[官解](https://hackmd.io/@mysh212/H1FMfv1VR)

[真正的官解程式碼](https://judge.citrc.tw/status/c2ea2723f3244bbe190ff47f3edb9eff)

### Statement

***Amberela*** 打算使用好多磁鐵排出 $x$ ，你可以幫他算算總共需要幾條磁鐵嗎？

以下依序紀錄排出 $[0,9]$ 所需的磁鐵數量:

[6,2,5,5,4,5,6,4,7,6]


### Input

輸入只有一個數字 $x$ ，代表 ***Amberela*** 想排的數字，

### Output

請輸出共需要多少磁鐵。

### Input Format

$x$

### Output Format

$Ans$

### Testcase
- Input 1

123

- Output 1

12

### Subtask
- Subtask 1 (50%) - $10^2 \leq x \leq (10^3 - 1)$
- Subtask 2 (50%) - ***As statement***
### Note

- $0 \leq x \leq (10^9)$
- $x$ 不會有前綴 $0$ 。

### Solution

### Code

- 滿分 by 橘子

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const vector<ll> a = {6,2,5,5,4,5,6,4,7,6};
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll ans = 0;
    string s;
    cin >> s;
    for(char c : s) ans += a[c-'0'];
    cout << ans << "\n";
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] a = {6,2,5,5,4,5,6,4,7,6};
        int ans = 0;
        String s = scanner.next();
        for (int c : s.chars().toArray()){
            ans += a[c-'0'];
        }
        System.out.println(ans);
        scanner.close();
    }
}

print(sum([6,2,5,5,4,5,6,4,7,6][int(c)] for c in input()))

## 地震 (Earthquake)
> 出題者：硫代硫酸鈉🌸
> 難度：p2
> 考點：二維陣列、窮舉

### Statement
最近實在是有太多地震了!可是硫代硫酸鈉卻一次警報都沒有收到，實在讓他很害怕。

於是呢，硫代硫酸鈉自行定義了一種整數搖晃程度單位 $m$ :「SCPA度」，為了增加精確度，劃分數值由 $0$ 到 $50$ 級。他定義座標 $x$ 軸向下為正，$y$ 軸向右取正，0-base，也定義 2D 平面上任兩點 $(a,b)$、$(c,d)$ 的水平距離就是 $\vert a-c \vert+\vert b-d \vert$。

這個搖晃程度大小又剛好和離震央水平距離、個人的所在的高度 $h$ 有密切的關係，無論當地高度為多少，震央高度一定為 $0$，水平距離每多 $1$，搖晃程度就少 $1$ 級，但高度每加 $1$，搖晃程度會多 $1$ 級。例如震央的「SCPA度」是 $3$ 級，有一地點與它的水平距離是 $5$，高度是 $4$，當地加上高度的的影響就會是 $2$ 級，若最終SCPA度小於 $0$，皆以 $0$ 計算。若大於 $50$，皆以 $50$ 計算。

因為「SCPA度」是硫代硫酸鈉定義的，並且他也有分享給他的好朋友們這個單位，所以只要一地震，他和他的好朋友們也都能立刻得知他們各自所在位置的「SCPA度」。硫代硫酸鈉想匯集這些資料後，推算出震央的座標和搖晃程度，並得知各個親戚居住地的搖晃程度，預警大家，你能幫他分析並回答他嗎?

### Input
輸入的第一行會包含四個正整數 $n$、$m$、$N$、$Q$，代表 $n * m$ 的地圖，$N$ 代表硫代硫酸鈉和他的好朋友總人數，$Q$ 代表他的親戚總人數。

接下來 $n$ 行中，每行有 $m$ 個數字，代表地圖各地的高度 $h_i$

再接下來 $N$ 行中，每行有 3 個數字 $x_i$、$y_i$、$m_i$，分別是座標的 $x$、$y$ 與當地搖晃程度 $m$。

最後 $Q$ 行中，每行有 $2$ 個數字 $x_i$、$y_i$，代表他親戚居住地的座標。

### Output
請輸出 $Q$ 行，每行輸出 $1$ 個整數，為親戚居住地的搖晃程度。

**資料範圍**
- $1 \leq n、m \leq 30$
- $3 \leq N \leq 50$
- $1 \leq Q \leq 50$
- $0 \leq h \leq 10$
- $0 \leq x、y \leq 29$
- 保證所有座標皆不重複，且恰只有一個合理的震央
- 震央產生的地震，SCPA度會界於 $1$ 到 $50$ 之間

### Testcase
- Input 1

4 5 4 2
0 3 2 5 1
4 2 0 3 4
1 4 0 1 3
2 5 1 2 4
1 2 3
0 2 4
1 3 5
2 1 5
0 3
3 1

- Output 1

6
5

- Input 2

7 9 10 5
0 4 7 6 1 2 10 3 8
6 5 3 3 1 0 0 6 8
3 0 7 2 0 3 9 6 8
8 7 10 2 3 2 9 7 5
3 6 1 3 2 5 10 10 9
6 9 1 9 1 10 1 9 0
4 0 9 7 1 1 0 10 2
1 8 0
3 1 8
2 0 4
2 4 0
3 6 5
3 8 0
2 5 0
1 7 0
6 0 9
0 2 4
1 4
3 2
5 5
4 4
0 0

- Output 2

0
10
9
1
0 

### Subtask
- Subtask 1 (50%) - 第一個座標為硫代硫酸鈉的所在地，剛好就是震央，且當地高度為0
- Subtask 2 (50%) - 無特殊限制
### Note
範例測資一說明：
去除高度的影響後，(1,2)的SCPA度為3、(0,2)為2、(1,3)為2、(2,1)為1
可得知震央在(1,2)，SCPA度為3
所求的(0,3)和(3,1)加上高度後的SCPA度分別為6和5

### Solution
- Subtask 1 : 直接讀入第一個座標、搖晃程度，再推算各地
- Subtask 2 : 窮舉每個地點，窮舉1~50的SCPA度，每檢查一個地點的一種SCPA度都要去檢查是否符合朋友的條件
### Code
- Subtask 1

#include<bits/stdc++.h>
using namespace std;
 
int n=0,m=0,N=0,Q=0;
int s[55][55]={};
int ansx=0,ansy=0,ansap=0;
 
struct point{
    int x=0;
    int y=0;
    int apcs=0;
 
    point(int inx,int iny,int inapcs){
        x=inx;
        y=iny;
        apcs=inapcs;
    }
};
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin>>n>>m>>N>>Q;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>s[i][j];
        }
    }
 
    cin>>ansx>>ansy>>ansap;
    for(int i=1;i<N;i++){
        int tmpx=0,tmpy=0,tmpap=0;
        cin>>tmpx>>tmpy>>tmpap;
    }
 
    for(int q=0;q<Q;q++){
        int qx=0,qy=0;
        cin>>qx>>qy;
        int ans=max(0,min(50,ansap-abs(ansx-qx)-abs(ansy-qy)+s[qx][qy]));
        cout<<ans<<(q==Q-1?"":"\n");
    }
}

- Subtask 1+2

#include<bits/stdc++.h>
using namespace std;

int n=0,m=0,N=0,Q=0;
int s[55][55]={};
int ansx=0,ansy=0,ansap=0;

struct point{
    int x=0;
    int y=0;
    int apcs=0;

    point(int inx,int iny,int inapcs){
        x=inx;
        y=iny;
        apcs=inapcs;
    }
};

vector<point> G;

void solve();

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin>>n>>m>>N>>Q;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>s[i][j];
        }
    }

    for(int i=0;i<N;i++){
        int tmpx=0,tmpy=0,tmpap=0;
        cin>>tmpx>>tmpy>>tmpap;
        point P=point(tmpx,tmpy,tmpap);
        G.push_back(P);
    }

    solve();

    for(int q=0;q<Q;q++){
        int qx=0,qy=0;
        cin>>qx>>qy;
        int ans=max(0,min(50,ansap-abs(ansx-qx)-abs(ansy-qy)+s[qx][qy]));
        cout<<ans<<(q==Q-1?"":"\n");
    }
}

void solve(){
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            for(int ap=1;ap<=50;ap++){
                for(int k=0;k<N;k++){
                    int sup=ap-abs(i-G[k].x)-abs(j-G[k].y)+s[G[k].x][G[k].y];
                    sup=max(0,min(50,sup));
                    if(sup!=G[k].apcs) break;
                    if(k==N-1){
                        ansx=i;
                        ansy=j;
                        ansap=ap;
                        return;
                    }
                }
            }
        }
    }
}

- 滿分 by 橘子

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const ll big = 1e18;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll n,M,c,q;
    cin >> n >> M >> c >> q;
    vector<vector<ll>> h(n,vector<ll>(M));
    for(auto &o : h) for(ll &i : o) cin >> i;
    vector<ll> x(c),y(c),m(c);
    for(ll i = 0;i<c;i++) cin >> x[i] >> y[i] >> m[i];
    for(ll a = 0;a<n;a++){
        for(ll b = 0;b<M;b++){
            for(ll w = 1;w<=50;w++){
                ll ok = 1;
                for(ll i = 0;i<c;i++){
                    ll cal = w-abs(a-x[i])-abs(b-y[i])+h[x[i]][y[i]];
                    cal = min(max(0ll,cal),50ll);
                    if (cal!=m[i]) ok = 0;
                }
                if(ok){
                    while(q--){
                        ll u,v;
                        cin >> u >> v;
                        ll cal = w-abs(a-u)-abs(b-v)+h[u][v];
                        cal = min(max(0ll,cal),50ll);
                        cout << cal << "\n";
                    }
                    return 0;
                }
            }
        }
    }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(),M=scanner.nextInt(),c=scanner.nextInt(),q=scanner.nextInt();
        int[][] h = new int[n][M];
        for(int a = 0;a<n;a++){
            for(int b = 0;b<M;b++){
                h[a][b] = scanner.nextInt();
            }
        }
        int[] x = new int[c];
        int[] y = new int[c];
        int[] m = new int[c];
        for(int i = 0;i<c;i++){
            x[i] = scanner.nextInt();
            y[i] = scanner.nextInt();
            m[i] = scanner.nextInt();
        }
        for(int a = 0;a<n;a++){
            for(int b = 0;b<M;b++){
                for(int w = 1;w<=50;w++){
                    boolean ok = true;
                    for(int i = 0;i<c;i++){
                        int cal = w-Math.abs(a-x[i])-Math.abs(b-y[i])+h[x[i]][y[i]];
                        cal = Math.min(Math.max(0,cal),50);
                        if (cal!=m[i]) ok = false;
                    }
                    if(ok){
                        for (int i = 0; i < q; i++) {
                            int u = scanner.nextInt(),v = scanner.nextInt();
                            int cal = w-Math.abs(a-u)-Math.abs(b-v)+h[u][v];
                            cal = Math.min(Math.max(0,cal),50);
                            System.out.println(""+cal);
                        }
                        System.exit(0);
                    }
                }
            }
        }
        scanner.close();
    }
}

N,M,n,q = map(int,input().split())
h = [list(map(int,input().split())) for _ in range(N)]
l = [list(map(int,input().split())) for _ in range(n)]
for a in range(N):
    for b in range(M):
        for w in range(1,51):
            for x,y,m in l:
                cal = w-abs(a-x)-abs(b-y)+h[x][y]
                cal = min(max(0,cal),50)
                if cal != m:
                    break
            else:
                for _ in range(q):
                    x,y = map(int,input().split())
                    cal = w-abs(a-x)-abs(b-y)+h[x][y]
                    cal = min(max(0,cal),50)
                    print(cal)
                break
        else:
            continue
        break
    else:
        continue
    break

print(*(lambda N,M,n,q:(lambda h,l,qs:next((min(max(0,w-abs(a-x)-abs(b-y)+h[x][y]),50) for x,y in qs) for a in range(N) for b in range(M) for w in range(1,51) if all(m==min(max(0,w-abs(a-x)-abs(b-y)+h[x][y]),50) for x,y,m in l)))([list(map(int,input().split())) for _ in range(N)],[list(map(int,input().split())) for _ in range(n)],[list(map(int,input().split())) for _ in range(q)]))(*map(int,input().split())),sep="\n")

## 大智慧學苑-來上體育課吧 (PE class)
> 出題者：Howard
> 難度：p3
> 考點：二分搜
### Statement
在大智慧學苑中，為了讓小朋友平時可以動一動，於是有一個區塊是可以讓小朋友跳來跳去的地方，會有一些板子散落在一條直線上，小朋友可以站在這些板子上跳來跳去的，但是當初在建造大智慧學苑的時候，這些被誤認為是給1歲小孩使用的，於是，有些板子和板子之間的距離超級近，這讓大智慧學苑的小朋友覺得太簡單，身為大智慧學苑院長Chung要來解決這個問題，但他真的很懶，只想把 $k$ 個板子搬走，為了可以預測最好的辦法，請寫一個程式模擬，在可以搬走 $k$ 個板子的情況下，板子和板子最小的距離可以到多大。
在這個跳格子的場地當中，小朋友會從位置 0 的地方出發，終點則是在位置 $T$。
### Input
第一行有三個數字 $N、K、T$ 一開始板子的數量，Chung想移開板子的數量，以及終點位置，中間以空白間隔開。
第二行開始有 $N$ 個數字 $(a_1,a_2,a_3,...,a_n)$ 代表每個板子一開始放置的位置，中間以空白間隔開，保證已排序。
$1\leq k\leq N \leq 10^3$
$N+1\leq T\leq 10^9$
$1\leq a_1 < a_2 < a_3 < ... < a_n <T$
### Output
輸出一個數字，在可以搬走 $k$ 個板子的情況下，板子和板子最小的距離可以到多大。
### Input Format
$N\ K\ T$
$a_1 \space a_2 \space \dots \space a_n$
### Output Format
$ans$
### Testcase
- Input 1

6 2 20
1 7 12 15 17 19

- Output 1

2

### Subtask
- Subtask 1 (30%) - $1\leq k\leq N \leq 160、N+1\leq T\leq 2\times 10^3$
- Subtask 2 (70%) - $1\leq k\leq N \leq 10^3、N+1\leq T\leq 1\times 10^9$
### Note
在第一組測資中，拿掉擺放於位置1和19的板子就可以使板子之間最小的距離最大
### Solution
- Subtask 1：這題可以直接枚舉板子跟板子之間的最小距離，然後從大到小枚舉，一旦枚舉到都符合板子跟板子間的距離，就可以輸出答案，並且可以保證這是最大的。
- Subtask 2：這題為一個非常經典的二分搜題目，我們可以發現，對於每個數字只要小於最後的答案，都會小於板子跟板子間的最小距離。接下來就直接把枚舉換成二分搜，就可以找到答案了。
### Code
- Subtask 1

#include<iostream>
using namespace std;
int main()
{
    int n, k, t;
    cin >> n >> k >> t;
    int v[n + 2] = {0};
    v[0] = 0, v[n + 1] = t;
    for(int i = 1; i <= n; i++) cin >> v[i];
    for(int j = t; j >= 0; j--) {
        int last = 0;
        int notuse = 0;
        for(int i = 1; i <= n + 1; i++) {
            if(v[i] - last < j) notuse++;
            else last = v[i];
        }   
        if(notuse <= k) {
            cout << j << '\n';
            return 0;
        }
    }
    return 0;
}

- Subtask 2

#include<iostream>
using namespace std;
int main()
{
    int n, k, t;
    cin >> n >> k >> t;
    int v[n + 2] = {0};
    v[0] = 0, v[n + 1] = t;
    for(int i = 1; i <= n; i++) cin >> v[i];
    int l = 0, r = t;
    while(r > l) {
        int mid = (l + r + 1) / 2;
        int last = 0;
        int notuse = 0;
        for(int i = 1; i <= n + 1; i++) {
            if(v[i] - last < mid) notuse++;
            else last = v[i];
        }
        if(notuse <= k) l = mid;
        else r = mid - 1;
    }
    cout << l << '\n';
    return 0;
}

- 滿分 by 橘子

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const ll big = 1e18;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll n,k,t;
    cin >> n >> k >> t;
    vector<ll> a(n);
    for(ll &i : a) cin >> i;
    ll l = 0,r = t/(n+1-k);
    while(l<r){
        ll x = l+r+1>>1;
        ll cnt = 0,last = 0;
        for(ll i : a){
            if (i-last>=x){
                last = i;
            }else{
                cnt++;
            }
        }
        cnt += t-last<x;
        if (cnt<=k){
            l = x;
        }else{
            r = x-1;
        }
    }
    cout << l << "\n";
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), k = scanner.nextInt(), t = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        int l = 0,r = t/(n+1-k);
        while (l<r){
            int x = l+r+1>>1;
            int cnt = 0,last = 0;
            for(int i : a){
                if (i-last>=x){
                    last = i;
                }else{
                    cnt++;
                }
            }
            if (t-last<x)cnt++;
            if (cnt<=k){
                l = x;
            }else{
                r = x-1;
            }
        }
        System.out.println(l);
        scanner.close();
    }
}

n,k,t = map(int,input().split())
a = list(map(int,input().split()))
l = 1
r = t//(n+1-k)
while l<r:
    x = l+r+1>>1
    last = 0
    cnt = 0
    for i in a:
        if i-last>=x:
            last = i
        else:
            cnt+=1
    if t-last<x:
        cnt+=1
    if cnt<=k:
        l = x
    else:
        r = x-1
print(l)

print((lambda n,k,t,a,o:o.__setitem__(1,t//(n+1-k)) or a.append(t) or any(o.__setitem__(2,0) or (o.__setitem__(0,x) if sum(i-o[2]<x or o.__setitem__(2,i) or 0 for i in a)<=k else o.__setitem__(1,x-1)) for x in iter(lambda:o[0]<o[1] and sum(o[:2])+1>>1,False)) or o[0])(*map(int,input().split()),list(map(int,input().split())),[1,1,0]))

## 電線 (Wire)
> 出題者：Mingyee
> 難度：P4
> 考點：樹DP
### Statement
Yee 星人的星球上有 $n$ 個城市

Yee 星人發現了一種室溫超導體，可以讓電無耗損傳播

於是他們規劃了一個供電網路，為了減少成本，他們以 $n-1$ 條電纜正好連接著 $n$ 個城市，使得不管發電機在哪個城市，每個城市都能獲得電的供應

不過實際應用後他們發現這個室溫超導體與理想狀況有些區別，電力實際只能傳播到**周遭以一條電纜連結**的城市

例如供電網路如下

1-2-3-4

若發電機在 $2$，電力只能傳播到 $1$ 和 $3$，而不能傳播到 $4$

於是無奈的 Yee 星人只好建造多個發電機解決這個問題

已知在第 $i$ 個城市建造發電機的成本為 $p_i$

不過 Yee 星人的城市十分龐大
所以他們聘請了與電神奮戰多年的你，幫他們撰寫一個城市來計算欲使所有城市獲得供電，所需要建造發電廠的**最低成本**

### Input

第一行輸入一個正整數 $n$，表示城市數量 $(1\le n \le 2 \times 10^5)$

接下來有 $n-1$ 行，每行輸入兩個**相異**正整數 $a$ $b$，表示城市 $a$ 與城市 $b$ 間有一條電纜連接 $(1 \le a, b \le n)$

第 $n+1$ 行輸入 $n$ 個整數，代表序列 $\lt p \gt$，其中 $p_i$ 代表在第 $i$ 個城市建造發電機的成本 $( 0\le p_i \le 10^9, 1 \le i \le n)$

所有測資保證供電網路中從任意城市出發，任意城市為終點，洽能找到**唯一**的一條電傳播路徑，且輸入無重複的 $(a, b)$

### Output
輸出一個正整數，代表使所有城市獲得電供應所需的最低成本

### Input Example
- Input 1

4
1 2
2 3
3 4
1 2 4 1

- Output 1

2

- Input 2

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

- Output 2

4

### Subtask
- Subtask 1 (30%) $n \le 20$
- Subtask 2 (20%) $\forall(a,b)\ a = b+1$ 且 $p_i = 1, (1 \le i \le n)$
- Subtask 3 (50%) 無其他限制

### Note

### Solution

### Code

### Subtask 1: 枚舉

### Subtask 2 :

n = int(input())
print( n//3 + (n%3 >0) , end = "")

### Subtask 3 樹DP
dp[x][0] 選x所需的最小值(以x為根，ignore所有父節點以上節點)
dp[x][1] 不選x且 不選x的父節點所需最小值
dp[x][2] 不選x且 選x的父節點所需最小值

答案= min(dp[rt][0], dp[rt][1]) (因為rt沒父節點)

#include <bits/stdc++.h>
#define int int64_t
#define endl "\n"
#define pb push_back
 
using namespace std;
constexpr int MAX_N = 2e5+5;
vector<int> G[MAX_N];
bool vis[MAX_N];
int dp[MAX_N][3];
int ans;
int dfs(int v, int p){
    bool mk = 0;
    int minn  = LLONG_MAX;
    for(auto a : G[v]){
        if(p == a) continue;
        dp[v][0] += dfs(a, v);
        dp[v][2] += min(dp[a][1], dp[a][0]);
        dp[v][1] += min(dp[a][1], dp[a][0]);

        if(dp[a][0] <= dp[a][1]) mk = 1;
        else minn = min(minn, dp[a][0] - dp[a][1]);
    }
    if(!mk) dp[v][1] += minn;
    //cout << "vis" << v << ' ' << dp[v][0] << ' ' << dp[v][1] <<  ' ' << dp[v][2] <<  endl;
    return min({dp[v][0], dp[v][1], dp[v][2]});
}
 

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, a, b;
    cin >> n;
    for(int x=0; x<n-1; x++){
        cin >> a >> b;
        G[a].pb(b);
        G[b].pb(a);
    }
    for(int x=1; x<=n; x++){
        cin >> dp[x][0];
    }
    dfs(1, 0);
    cout << min(dp[1][0], dp[1][1]);
    return 0;
}

### 稍微不同的DP定義 by 橘子

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const ll big = 1e18;
struct obj{
    ll a,b,c; // choose has no
};
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll n;
    cin >> n;
    vector<vector<ll>> con(n);
    for(ll i = 1;i<n;i++){
        ll u,v;
        cin >> u >> v;
        con[u-1].push_back(v-1);
        con[v-1].push_back(u-1);
    }
    vector<ll> a(n);
    for(ll &i : a) cin >> i;
    function<obj(ll,ll)> dfs;
    dfs = [&](ll i, ll p){
        ll s1 = 0, s2 = 0, s3 = big;
        for(ll j : con[i]) if(j!=p){
            obj o = dfs(j,i);
            s1 += o.c;
            s2 += o.b;
            s3 = min(s3,o.a-o.b);
        }
        obj ret = {s1+a[i],s2+s3,s2};
        ret.b = min(ret.b,ret.a);
        ret.c = min(ret.c,ret.b);
        return ret;
    };
    obj o = dfs(0,-1);
    cout << o.b << "\n";
}

import java.util.*;

public class Main {
    static int n;
    static ArrayList<ArrayList<Integer>> con;
    static int[] a;
    public static int[] dfs(int i, int p){
        int s1 = 0,s2 = 0,s3 = 1000000000;
        for(int j : con.get(i))if(j != p){
            int[] o = dfs(j,i);
            s1 += o[2];
            s2 += o[1];
            s3 = Math.min(s3,o[0]-o[1]);
        }
        int[] ret = new int[]{s1+a[i],s2+s3,s2};
        ret[1] = Math.min(ret[1],ret[0]);
        ret[2] = Math.min(ret[2],ret[1]);
        return ret;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        con = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            con.add(new ArrayList<>());
        }
        for (int i = 0; i < n-1; i++) {
            int u = scanner.nextInt()-1, v = scanner.nextInt()-1;
            con.get(u).add(v);
            con.get(v).add(u);
        }
        a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        System.out.println(dfs(0,-1)[1]);
        scanner.close();
    }
}

import sys
sys.setrecursionlimit(1000000)
n = int(input())
con = [[] for _ in range(n)]
for _ in range(n-1):
    u,v = map(int,input().split())
    con[u-1].append(v-1)
    con[v-1].append(u-1)
a = list(map(int,input().split()))
def dfs(i,p):
    s1 = 0
    s2 = 0
    s3 = 10**10
    for j in con[i]:
        if j != p:
            o = dfs(j,i)
            s1 += o[2]
            s2 += o[1]
            s3 = min(s3,o[0]-o[1])
    ret = [s1+a[i],s2+s3,s2]
    ret[1] = min(ret[1],ret[0])
    ret[2] = min(ret[2],ret[1])
    return ret
print(dfs(0,-1)[1])

print((lambda n,f,fs:(lambda ls,con,a:any(con[u-1].append(v-1) or con[v-1].append(u-1) for u,v in ls) or (lambda dfs:dfs(dfs,0,-1)[1])(lambda dfs,i,p:(lambda l:(l[0]+a[i],min(l[0]+a[i],l[1]+l[2]),min(l[0]+a[i],l[1])))([fs[i](o) for i,o in enumerate(zip(*(f(dfs(dfs,j,i)) if j != p else (0,0,10**10) for j in con[i])))])))(list(map(int,input().split()) for _ in range(n-1)),[[] for _ in range(n)],list(map(int,input().split()))))(int(input()),(lambda o:(o[2],o[1],o[0]-o[1])),(sum,sum,min)))