func_code_string: #include <bits/stdc++.h>   using namespace std;   vector<int> v[150005];   int Size[150005];   int forbid[150005];   int val[150005];   vector<int> stk;   void dfs(int first, int f) {     Size[first] = 1;     stk.push_back(first);     for (auto it : v[first]) {       if (it != f && !forbid[it]) {         dfs(it, first);         Size[first] += Size[it];       }     }   }   bool cmp(const int &a, const int &b) { return Size[a] < Size[b]; }   int find_cen(int first) {     stk.clear();     dfs(first, 0);     sort(stk.begin(), stk.end(), cmp);     for (auto it : stk) {       if (Size[it] >= Size[first] / 2) {         return it;       }     }   }   long long ans;   vector<pair<long long, long long> > vv;   void dfs2(int first, int f, long long sum, long long sum2, long long len) {     sum += val[first];     sum2 += sum;     vv.push_back(make_pair(len, sum2));     for (auto it : v[first]) {       if (it != f && !forbid[it]) {         dfs2(it, first, sum, sum2, len + 1);       }     }   }   void dfs3(int first, int f, long long sum, long long sum2, long long len) {     sum += val[first];     sum2 += val[first] * len;     vv.push_back(make_pair(sum, sum2));     for (auto it : v[first]) {       if (it != f && !forbid[it]) {         dfs3(it, first, sum, sum2, len + 1);       }     }   }   struct DATA {     long long first, second, st;   };   int op;   bool operator<(const DATA &p, const DATA &q) {     if (op == 0)       return p.first < q.first;     else       return p.st < q.st;   }   void go(int first) {     int cen = find_cen(first);     set<DATA> s;     for (int t = 0; t < 2; t++) {       s.insert({0, 0, -1000000000});       for (auto first : v[cen]) {         if (forbid[first]) continue;         dfs2(first, cen, val[cen], val[cen], 2);         op = 1;         for (auto p : vv) {           if (s.empty()) break;           auto it = prev(s.upper_bound({0, 0, p.first}));           ans = max(ans, p.first * it->first + it->second + p.second);         }         vv.clear();         dfs3(first, cen, 0, 0, 1);         op = 0;         for (auto p : vv) {           auto it = s.lower_bound({p.first, p.second, 0});           if (it != s.end() && it->first == p.first) {             if (it->second > p.second)               continue;             else {               s.erase(*it);               it = s.lower_bound({p.first, p.second, 0});             }           }           while (it != s.end()) {             DATA d = *it;             auto it2 = next(it);             s.erase(it);             it = it2;             long long st = (p.second - d.second) / (d.first - p.first);             d.st = st;             if (it == s.end() || it->st > st) {               s.insert(d);               break;             }           }           it = s.lower_bound({p.first, p.second, 0});           int st = -1e9;           while (it != s.begin()) {             DATA d = *prev(it);             st = (d.second - p.second) / (p.first - d.first);             if (st <= d.st) {               s.erase(d);             } else {               break;             }           }           if (it == s.end() || it->st > st) s.insert({p.first, p.second, st});         }         vv.clear();       }       reverse(v[cen].begin(), v[cen].end());       s.clear();     }     forbid[cen] = 1;     for (auto it : v[cen]) {       if (!forbid[it]) {         go(it);       }     }   }   int main() {     int n;     scanf( %d , &n);     for (int i = 1; i < n; i++) {       int first, second;       scanf( %d %d , &first, &second);       v[first].push_back(second);       v[second].push_back(first);     }     for (int i = 1; i <= n; i++) scanf( %d , &val[i]);     go(1);     printf( %lld n , ans);   }   