func_code_string: #include <bits/stdc++.h>   template <typename Tp>   inline void read(Tp &x) {     x = 0;     bool f = true;     char ch = getchar();     for (; ch <  0  || ch >  9 ; ch = getchar()) f ^= ch ==  - ;     for (; ch >=  0  && ch <=  9 ; ch = getchar()) x = x * 10 + (ch ^ 48);     x = f ? x : -x;   }   const int N = 15e4;   struct Node {     long long k, b;     bool exist;   };   struct Segment_Tree {     Node Tre[N * 4 + 5];     void build(int p, int l, int r) {       Tre[p].k = Tre[p].b = 0, Tre[p].exist = false;       if (l == r) return;       int mid = (l + r) >> 1;       build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);     }     void update(int p, int l, int r, long long k, long long b) {       if (!Tre[p].exist) {         Tre[p].exist = true;         Tre[p].k = k, Tre[p].b = b;         return;       }       long long l1 = k * l + b, r1 = k * r + b, l2 = Tre[p].k * l + Tre[p].b,                 r2 = Tre[p].k * r + Tre[p].b;       if (l1 <= l2 && r1 <= r2) return;       if (l1 >= l2 && r1 >= r2) {         Tre[p].k = k, Tre[p].b = b;         return;       }       double x = 1.0 * (b - Tre[p].b) / (Tre[p].k - k);       int mid = (l + r) >> 1;       if (l1 > l2) {         if (x <= mid)           update(p << 1, l, mid, k, b);         else {           update(p << 1 | 1, mid + 1, r, Tre[p].k, Tre[p].b);           Tre[p].k = k, Tre[p].b = b;         }       } else {         if (x <= mid) {           update(p << 1, l, mid, Tre[p].k, Tre[p].b);           Tre[p].k = k, Tre[p].b = b;         } else           update(p << 1 | 1, mid + 1, r, k, b);       }     }     long long query(int p, int l, int r, int x) {       if (l == r) return Tre[p].k * x + Tre[p].b;       int mid = (l + r) >> 1;       long long res = Tre[p].k * x + Tre[p].b;       if (x <= mid)         return std::max(res, query(p << 1, l, mid, x));       else         return std::max(res, query(p << 1 | 1, mid + 1, r, x));     }   };   Segment_Tree T;   int a[N + 5], siz[N + 5], rt, SZ, Max;   bool vis[N + 5];   long long ans;   std::vector<int> Vec[N + 5];   void find(int u, int ff) {     siz[u] = 1;     int mx = 0;     for (int i = 0; i < (int)Vec[u].size(); ++i) {       int v = Vec[u][i];       if (v == ff || vis[v]) continue;       find(v, u);       siz[u] += siz[v];       mx = std::max(mx, siz[v]);     }     mx = std::max(mx, SZ - siz[u]);     if (mx < Max) Max = mx, rt = u;   }   int m;   void dfs1(int u, int ff, int dep) {     m = std::max(m, dep);     for (int i = 0; i < (int)Vec[u].size(); ++i) {       int v = Vec[u][i];       if (vis[v] || v == ff) continue;       dfs1(v, u, dep + 1);     }   }   void dfs2(int u, int ff, long long sum, long long ssum, int dep) {     ssum += sum + a[u];     int cnt = 0;     for (int i = 0; i < (int)Vec[u].size(); ++i) {       int v = Vec[u][i];       if (v == ff || vis[v]) continue;       ++cnt;       dfs2(v, u, sum + a[u], ssum, dep + 1);     }     if (!cnt) ans = std::max(ans, ssum + T.query(1, 1, m, dep));   }   void dfs3(int u, int ff, long long sum, long long ssum, int dep) {     sum += a[u];     ssum += 1LL * dep * a[u];     int cnt = 0;     for (int i = 0; i < (int)Vec[u].size(); ++i) {       int v = Vec[u][i];       if (v == ff || vis[v]) continue;       ++cnt;       dfs3(v, u, sum, ssum, dep + 1);     }     if (!cnt) T.update(1, 1, m, sum, ssum);   }   inline void solve(int u) {     m = 0;     dfs1(u, 0, 1);     T.build(1, 1, m);     for (int i = 0; i < (int)Vec[u].size(); ++i) {       int v = Vec[u][i];       if (vis[v]) continue;       dfs2(v, u, a[u], a[u], 2);       dfs3(v, u, 0, 0, 1);     }     T.build(1, 1, m);     for (int i = (int)Vec[u].size() - 1; i >= 0; --i) {       int v = Vec[u][i];       if (vis[v]) continue;       dfs2(v, u, a[u], a[u], 2);       dfs3(v, u, 0, 0, 1);     }     ans = std::max(ans, a[u] + T.query(1, 1, m, 1));   }   void divide(int u) {     solve(u);     vis[u] = true;     for (int i = 0; i < (int)Vec[u].size(); ++i) {       int v = Vec[u][i];       if (vis[v]) continue;       SZ = Max = siz[v];       find(v, 0);       divide(rt);     }   }   int main() {     int n;     read(n);     for (int i = 1; i < n; ++i) {       int u, v;       read(u), read(v);       Vec[u].push_back(v), Vec[v].push_back(u);     }     for (int i = 1; i <= n; ++i) read(a[i]);     Max = SZ = n;     find(1, 0);     divide(rt);     printf( %lld n , ans);     return 0;   }   