#include #ifndef DUMP #define DUMP(...) void(0) #endif using namespace std; struct graph { struct edge { static inline bool cost; int src, dst; int operator-(int v) const { return src ^ dst ^ v; } }; int n, m; vector edges; vector>> adj; graph(int _n = 0) : n(_n), m(0), adj(n) {} int add(const edge& e, bool directed = false) { edges.push_back(e); adj[e.src].emplace_back(m, e.dst); if (not directed) adj[e.dst].emplace_back(m, e.src); return m++; } }; struct dfs_forest : graph { using T = decltype(edge::cost); vector root, pv, pe, sz, dep, min_dep, last, ord, in, out; vector dist; int trials; dfs_forest(int _n = 0) : graph(_n), dist(n), trials(0) { for (auto p : {&root, &pv, &pe, &sz, &dep, &min_dep, &last, &in, &out}) p->assign(n, -1); } int add(const edge& e) { return graph::add(e); } void dfs(int v) { sz[v] = 1, min_dep[v] = dep[v], last[v] = trials; in[v] = size(ord), ord.push_back(v); for (auto [id, u] : adj[v]) { if (id == pe[v]) continue; if (last[u] == trials) { min_dep[v] = min(min_dep[v], dep[u]); continue; } root[u] = root[v], pv[u] = v, pe[u] = id, dep[u] = dep[v] + 1; dist[u] = dist[v] + edges[id].cost; dfs(u); sz[v] += sz[u], min_dep[v] = min(min_dep[v], min_dep[u]); } out[v] = size(ord); } void build(int r, bool clear_ord = true) { root[r] = r, pv[r] = pe[r] = -1, dep[r] = 0, dist[r] = T{}; if (clear_ord) ord.clear(); dfs(r); ++trials; } void build() { fill(begin(root), end(root), -1); for (int v = 0; v < n; ++v) if (root[v] == -1) build(v, v == 0); } int farther(int id) const { int u = edges[id].src, v = edges[id].dst; return dep[u] < dep[v] ? v : u; } bool spans(int id) const { return id == pe[farther(id)]; } bool anc(int u, int v) const { return in[u] <= in[v] and out[v] <= out[u]; } }; struct hld_forest : dfs_forest { vector head; hld_forest(int _n = 0) : dfs_forest(_n), head(n) {} void dfs_hld(int v) { in[v] = size(ord), ord.push_back(v); sort(begin(adj[v]), end(adj[v]), [&](auto a, auto b) { int au = a.second, bu = b.second; return (a.first == pe[au]) * sz[au] > (b.first == pe[bu]) * sz[bu]; }); for (auto [id, u] : adj[v]) { if (id == pe[v] or not spans(id)) continue; head[u] = u == adj[v][0].second ? head[v] : u; dfs_hld(u); } out[v] = size(ord); } void build_hld(int r, bool clear_ord = true) { build(r, clear_ord); ord.erase(end(ord) - sz[r], end(ord)); head[r] = r; dfs_hld(r); } void build_hld() { fill(begin(root), end(root), -1); for (int v = 0; v < n; ++v) if (root[v] == -1) build_hld(v, v == 0); } int lca(int u, int v) const { assert(root[u] == root[v]); while (true) { if (in[u] > in[v]) swap(u, v); if (head[u] == head[v]) return u; v = pv[head[v]]; } } int d(int u, int v) const { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; } T distance(int u, int v) const { return dist[u] + dist[v] - 2 * dist[lca(u, v)]; } int la(int v, int d) const { assert(0 <= d), assert(d <= dep[v]); while (dep[head[v]] > d) v = pv[head[v]]; return ord[in[head[v]] + (d - dep[head[v]])]; } int next(int src, int dst) const { assert(root[src] == root[dst]), assert(src != dst); if (not anc(src, dst)) return pv[src]; return la(dst, dep[src] + 1); } int next(int src, int dst, int k) const { assert(root[src] == root[dst]), assert(k >= 0); int v = lca(src, dst); if (k <= dep[src] - dep[v]) return la(src, dep[src] - k); k -= dep[src] - dep[v]; assert(k <= dep[dst] - dep[v]); return la(dst, dep[v] + k); } vector> ascend(int src, int dst) const { vector> res; while (head[src] != head[dst]) { res.emplace_back(in[src], in[head[src]]); src = pv[head[src]]; } if (src != dst) res.emplace_back(in[src], in[dst] + 1); return res; } vector> descend(int src, int dst) const { if (src == dst) return {}; if (head[src] == head[dst]) return {{in[src] + 1, in[dst]}}; auto res = descend(src, pv[head[dst]]); res.emplace_back(in[head[dst]], in[dst]); return res; } template void run(int src, int dst, F f, bool vertex = true) const { assert(root[src] == root[dst]); int v = lca(src, dst); for (auto [a, b] : ascend(src, v)) f(a + 1, b); if (vertex) f(in[v], in[v] + 1); for (auto [a, b] : descend(v, dst)) f(a, b + 1); } }; int main() { cin.tie(nullptr)->sync_with_stdio(false); int n, k; cin >> n >> k; vector pos(k), val(k); for (auto&& e : pos) cin >> e, --e; for (auto&& e : val) cin >> e; hld_forest g(n); for (int _ = n - 1; _--;) { int u, v; cin >> u >> v; --u, --v; g.add({u, v}); } g.build_hld(); vector pref(k + 1); for (int i = 0; i < k; ++i) pref[i + 1] = pref[i] + val[i]; vector suff(k + 1); for (int i = k; i--;) suff[i] = val[i] + suff[i + 1]; assert(k >= 2); int lca = g.lca(pos[0], pos.back()); vector pref_lca(k + 1, lca), pref_depth(k + 1, g.dep[lca]); for (int i = 0; i < k; ++i) { pref_lca[i + 1] = g.lca(pref_lca[i], pos[i]); pref_depth[i + 1] = g.dep[pref_lca[i + 1]]; } vector suff_lca(k + 1, lca), suff_depth(k + 1, g.dep[lca]); for (int i = k; i--;) { suff_lca[i] = g.lca(pos[i], suff_lca[i + 1]); suff_depth[i] = g.dep[suff_lca[i]]; } DUMP(pref_depth); DUMP(suff_depth); constexpr int64_t inf = 1e15; auto check = [&](auto m) -> bool { int64_t cnt = pref.back() + pref_depth.back() < m; { int cur = -1; for (int l = 0, r = k; l < r; ++l) { cnt += pref[l] + (cur != -1 ? g.dep[cur] : -inf) < m; cur = cur != -1 ? g.lca(cur, pos[l]) : pos[l]; } } { int cur = -1; for (int l = 0, r = k; l < r; --r) { cnt += r < k and suff[r] + (cur != -1 ? g.dep[cur] : -inf) < m; cur = cur != -1 ? g.lca(cur, pos[r - 1]) : pos[r - 1]; } } for (int r = 1; r < k; ++r) for (int l = 1; l < r; ++l) { cnt += pref[l] + suff[r] + min(pref_depth[l], suff_depth[r]) < m; } return cnt <= int64_t(k) * (k + 1) / 4; }; int64_t ok = -inf, ng = inf; while (ng - ok > 1) { auto mid = (ok + ng) / 2; (check(mid) ? ok : ng) = mid; } cout << ok << '\n'; }