#include using namespace std; #define _p(...) (void)printf(__VA_ARGS__) #define forr(x,arr) for(auto&& x:arr) #define _overload3(_1,_2,_3,name,...) name #define _rep2(i,n) _rep3(i,0,n) #define _rep3(i,a,b) for(int i=int(a);i=int(a);i--) #define rrep(...) _overload3(__VA_ARGS__,_rrep3,_rrep2,)(__VA_ARGS__) #define ALL(x) (x).begin(), (x).end() #define BIT(n) (1LL<<(n)) #define SZ(x) ((int)(x).size()) #define fst first #define snd second typedef vector vi;typedef vector vvi;typedef pair pii;typedef vector vpii; typedef long long ll; class LCA { public: int H, W; vector > parent; vector depth; // LCA(木の頂点数) LCA(int V, vector >& E) : W(V), depth(V) { H = 1; while (1 << H < W) H++; parent.resize(H, vector(W)); // 適当な頂点からdfsして親を求めておく dfs(E, 0, -1, 0); // 親をダブリングする for (int k = 1; k < H; k++) { for (int v = 0; v < W; v++) { parent[k][v] = parent[k-1][v] == -1 ? -1 : parent[k-1][parent[k-1][v]]; } } } void dfs(vector >& E, int cur, int par, int dep) { parent[0][cur] = par; depth[cur] = dep; for (int i = 0; i < (int) E[cur].size(); i++) { if (E[cur][i] != par) dfs(E, E[cur][i], cur, dep + 1); } } // u と v の LCA を求める int query(int u, int v) { // 深い方を v にしておく if (depth[u] > depth[v]) swap(u, v); // 根からの深さが u と同じになるまで v の親をたどる for (int k = 0; k < H; k++) { if ((depth[v]-depth[u]) >> k & 1) { v = parent[k][v]; } } if (u == v) return u; // 二分探索でLCAを求める for (int k = H - 1; k >= 0; k--) { if (parent[k][u] != parent[k][v]) { u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } }; vi U; vvi E; vi tax; void dfs(int cur, int pre, int ct) { tax[cur] = ct + U[cur]; forr(nex, E[cur]) { if (nex != pre) { dfs(nex, cur, ct + U[cur]); } } } void Main() { int N; scanf("%d", &N); E.resize(N); tax.resize(N); rep(i,N-1) { int a, b; scanf("%d%d", &a, &b); E[a].push_back(b); E[b].push_back(a); } U.resize(N); rep(i, N) scanf("%d", &U[i]); LCA lca(N, E); tax.resize(N); dfs(0, -1, 0); //rep(i,SZ(tax)) cout<<"tax["<