func_code_string: #include <bits/stdc++.h>   using namespace std;   void fastscan(int& number) {     bool negative = false;     register int c;     number = 0;     c = getchar();     while (c == 10) c = getchar();     if (c ==  - ) {       negative = true;       c = getchar();     }     for (; (c > 47 && c < 58); c = getchar()) number = number * 10 + c - 48;     if (negative) number *= -1;   }   const int N = 150005;   struct line {     long long k, b;     line(long long K = 0, long long B = -1000000007ll * 1000000007ll) {       k = K;       b = B;     }   };   long long f(line p, long long x) { return p.k * x + p.b; }   line t[4 * N];   void cl(int k) {     k++;     k *= 4;     for (int i = 1; i <= k; i++) t[i] = line();   }   void add(int v, int l, int r, line p) {     int m = (l + r) / 2;     bool M = f(p, m) > f(t[v], m);     bool L = f(p, l) > f(t[v], l);     if (M) swap(p, t[v]);     if (r - l == 1) return;     if (L != M)       add(v * 2, l, m, p);     else       add(v * 2 + 1, m, r, p);   }   long long get(int v, int l, int r, int pos) {     if (r - l == 1) return f(t[v], pos);     int m = (l + r) / 2;     if (pos <= m)       return max(f(t[v], pos), get(v * 2, l, m, pos));     else       return max(f(t[v], pos), get(v * 2 + 1, m, r, pos));   }   int n, used[N], color[N], cnt[N], col;   long long a[N], ans;   vector<int> g[N];   void dfsCnt(int v, int p) {     cnt[v] = 1;     for (int i = 0; i < g[v].size(); i++) {       int to = g[v][i];       if (used[to] || to == p) continue;       dfsCnt(to, v);       cnt[v] += cnt[to];     }   }   int centr(int u) {     dfsCnt(u, 0);     col++;     queue<int> q;     q.push(u);     while (!q.empty()) {       int v = q.front();       q.pop();       color[v] = col;       int can = 1;       if (!can) continue;       for (int i = 0; i < g[v].size(); i++) {         int to = g[v][i];         if (used[to] || color[to] == col) continue;         if (!(cnt[u] >= 2 * cnt[to])) {           q.push(to);           can = 0;         }       }       if (can) {         used[v] = 1;         return v;       }     }     assert(0);   }   vector<line> upd;   long long pr[N], sum1[N], sum2[N], st;   int k;   void dfs(int v, int p, int d) {     pr[v] = pr[p] + a[v];     sum1[v] = sum1[p] + d * a[v];     sum2[v] = sum2[p] + pr[v];     cnt[v] = 1;     ans = max(ans, get(1, 0, k, d - 1) + sum2[v] - st * d);     ans = max(ans, sum1[v]);     upd.push_back(line(pr[v], sum1[v]));     for (int i = 0; i < g[v].size(); i++) {       int to = g[v][i];       if (used[to] || to == p) continue;       dfs(to, v, d + 1);       cnt[v] += cnt[to];     }   }   void solve(int v, int K) {     v = centr(v);     k = max(K, 1);     pr[v] = sum1[v] = sum2[v] = st = a[v];     for (int i = 0; i < g[v].size(); i++) {       int to = g[v][i];       if (used[to]) continue;       dfs(to, v, 2);       while (!upd.empty()) {         add(1, 0, k, upd.back());         upd.pop_back();       }     }     cl(k);     for (int i = g[v].size() - 1; i >= 0; i--) {       int to = g[v][i];       if (used[to]) continue;       dfs(to, v, 2);       while (!upd.empty()) {         add(1, 0, k, upd.back());         upd.pop_back();       }     }     cl(k);     for (int i = 0; i < g[v].size(); i++) {       int to = g[v][i];       if (used[to]) continue;       solve(to, cnt[to] / 2 + 1);     }   }   int main() {     cin >> n;     for (int i = 2; i <= n; i++) {       int a, b;       fastscan(a);       fastscan(b);       g[a].push_back(b);       g[b].push_back(a);     }     for (int i = 1; i <= n; i++) {       int x;       fastscan(x);       a[i] = x;     }     solve(1, n / 2 + 1);     cout << ans << endl;     return 0;   }   