#define _USE_MATH_DEFINES #include using namespace std; #define FOR(i,m,n) for(int i=(m);i<(n);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() using ll = long long; constexpr int INF = 0x3f3f3f3f; constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL; constexpr double EPS = 1e-8; constexpr int MOD = 1000000007; // constexpr int MOD = 998244353; constexpr int DY[]{1, 0, -1, 0}, DX[]{0, -1, 0, 1}; constexpr int DY8[]{1, 1, 0, -1, -1, -1, 0, 1}, DX8[]{0, -1, -1, -1, 0, 1, 1, 1}; template inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; } template inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; } struct IOSetup { IOSetup() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << fixed << setprecision(20); } } iosetup; struct EulerTour { std::vector tour, left, right, down, up, depth; EulerTour(const std::vector> &graph, int root = 0) : graph(graph) { int n = graph.size(); left.resize(n); right.resize(n); down.assign(n, -1); up.assign(n, (n - 1) << 1); int idx = 0; dfs(-1, root, 0, idx); } template void v_update(int ver, Fn f) const { f(left[ver], right[ver] + 1); } template T v_query(int ver, Fn f) const { return f(left[ver], right[ver] + 1); } template T e_query(int u, int v, Fn f) const { return f(down[u] + 1, down[v] + 1); } template void subtree_e_update(int ver, Fn f) const { f(down[ver] + 1, up[ver]); } template T subtree_e_query(int ver, Fn f) const { return f(down[ver] + 1, up[ver]); } private: const std::vector> graph; void dfs(int par, int ver, int now_depth, int &idx) { left[ver] = tour.size(); tour.emplace_back(ver); depth.emplace_back(now_depth); for (int e : graph[ver]) { if (e != par) { down[e] = idx++; dfs(ver, e, now_depth + 1, idx); tour.emplace_back(ver); depth.emplace_back(now_depth); up[e] = idx++; } } right[ver] = tour.size() - 1; } }; struct LowestCommonAncestorByDoubling { std::vector depth, dist; LowestCommonAncestorByDoubling(const std::vector> &graph) : graph(graph) { n = graph.size(); depth.resize(n); dist.resize(n); while ((1 << table_h) <= n) ++table_h; parent.resize(table_h, std::vector(n)); } void build(int root = 0) { is_built = true; dfs(-1, root, 0, 0); for (int i = 0; i + 1 < table_h; ++i) for (int ver = 0; ver < n; ++ver) { parent[i + 1][ver] = parent[i][ver] == -1 ? -1 : parent[i][parent[i][ver]]; } } int query(int u, int v) const { assert(is_built); if (depth[u] > depth[v]) std::swap(u, v); for (int i = 0; i < table_h; ++i) { if ((depth[v] - depth[u]) >> i & 1) v = parent[i][v]; } if (u == v) return u; for (int i = table_h - 1; i >= 0; --i) { if (parent[i][u] != parent[i][v]) { u = parent[i][u]; v = parent[i][v]; } } return parent[0][u]; } int distance(int u, int v) const { assert(is_built); return dist[u] + dist[v] - dist[query(u, v)] * 2; } private: bool is_built = false; int n, table_h = 1; std::vector> graph, parent; void dfs(int par, int ver, int now_depth, int now_dist) { depth[ver] = now_depth; dist[ver] = now_dist; parent[0][ver] = par; for (int e : graph[ver]) { if (e != par) dfs(ver, e, now_depth + 1, now_dist + 1); } } }; struct HeavyLightDecomposition { std::vector parent, subtree, id, inv, head; HeavyLightDecomposition(const std::vector> &graph, int root = 0) : graph(graph) { int n = graph.size(); parent.assign(n, -1); subtree.assign(n, 1); id.resize(n); inv.resize(n); head.resize(n); dfs1(root); head[root] = root; int now_id = 0; dfs2(root, now_id); } template void v_update(int u, int v, Fn f) const { while (true) { if (id[u] > id[v]) std::swap(u, v); f(std::max(id[head[v]], id[u]), id[v] + 1); if (head[u] == head[v]) return; v = parent[head[v]]; } } template T v_query(int u, int v, F f, G g, const T ID) const { T left = ID, right = ID; while (true) { if (id[u] > id[v]) { std::swap(u, v); std::swap(left, right); } left = g(left, f(std::max(id[head[v]], id[u]), id[v] + 1)); if (head[u] == head[v]) break; v = parent[head[v]]; } return g(left, right); } template void subtree_v_update(int ver, Fn f) const { f(id[ver], id[ver] + subtree[ver]); } template T subtree_v_query(int ver, Fn f) const { return f(id[ver], id[ver] + subtree[ver]); } template void e_update(int u, int v, Fn f) const { while (true) { if (id[u] > id[v]) std::swap(u, v); if (head[u] == head[v]) { f(id[u], id[v]); break; } else { f(id[head[v]] - 1, id[v]); v = parent[head[v]]; } } } template T e_query(int u, int v, F f, G g, const T ID) const { T left = ID, right = ID; while (true) { if (id[u] > id[v]) { std::swap(u, v); std::swap(left, right); } if (head[u] == head[v]) { left = g(left, f(id[u], id[v])); break; } else { left = g(left, f(id[head[v]] - 1, id[v])); v = parent[head[v]]; } } return g(left, right); } template void subtree_e_update(int ver, Fn f) const { f(id[ver], id[ver] + subtree[ver] - 1); } template T subtree_e_query(int ver, Fn f) const { return f(id[ver], id[ver] + subtree[ver] - 1); } int lowest_common_ancestor(int u, int v) const { while (true) { if (id[u] > id[v]) std::swap(u, v); if (head[u] == head[v]) return u; v = parent[head[v]]; } } private: std::vector> graph; void dfs1(int ver) { for (int &e : graph[ver]) { if (e != parent[ver]) { parent[e] = ver; dfs1(e); subtree[ver] += subtree[e]; if (subtree[e] > subtree[graph[ver].front()]) std::swap(e, graph[ver].front()); } } } void dfs2(int ver, int &now_id) { id[ver] = now_id++; inv[id[ver]] = ver; for (int e : graph[ver]) { if (e != parent[ver]) { head[e] = (e == graph[ver].front() ? head[ver] : e); dfs2(e, now_id); } } } }; template struct FenwickTreeSupportingRangeAddQuery { FenwickTreeSupportingRangeAddQuery(int n_, const Abelian ID = 0) : n(n_), ID(ID) { ++n; dat_const.assign(n, ID); dat_linear.assign(n, ID); } void add(int left, int right, Abelian val) { if (right < ++left) return; for (int i = left; i < n; i += i & -i) { dat_const[i] -= val * (left - 1); dat_linear[i] += val; } for (int i = right + 1; i < n; i += i & -i) { dat_const[i] += val * right; dat_linear[i] -= val; } } Abelian sum(int idx) const { Abelian res = ID; for (int i = idx; i > 0; i -= i & -i) res += dat_linear[i]; res *= idx; for (int i = idx; i > 0; i -= i & -i) res += dat_const[i]; return res; } Abelian sum(int left, int right) const { return left < right ? sum(right) - sum(left) : ID; } Abelian operator[](const int idx) const { return sum(idx, idx + 1); } private: int n; const Abelian ID; std::vector dat_const, dat_linear; }; int main() { int n, k; cin >> n >> k; vector> graph(n); REP(_, n - 1) { int u, v; cin >> u >> v; --u; --v; graph[u].emplace_back(v); graph[v].emplace_back(u); } vector d(k); REP(i, k) cin >> d[i], --d[i]; EulerTour euler_tour(graph, d.front()); sort(ALL(d), [&](int a, int b) -> bool { return euler_tour.left[a] < euler_tour.left[b]; }); // REP(i, k) cerr << d[i] << " \n"[i + 1 == k]; LowestCommonAncestorByDoubling lca(graph); lca.build(d.front()); ll steiner = 0; REP(i, k) steiner += lca.distance(d[i], d[(i + 1) % k]); // cerr << steiner << '\n'; HeavyLightDecomposition hld(graph, d.front()); FenwickTreeSupportingRangeAddQuery bit(n); REP(i, k) hld.v_update(d[i], d[(i + 1) % k], [&](int u, int v) -> void { bit.add(u, v, 1); }); vector dist(n, -1), from(n, -1); queue que; REP(i, n) { if (bit[hld.id[i]] > 0) { dist[i] = 0; from[i] = i; que.emplace(i); } } while (!que.empty()) { int ver = que.front(); que.pop(); for (int e : graph[ver]) { if (dist[e] == -1) { dist[e] = dist[ver] + 1; from[e] = from[ver]; que.emplace(e); } } } // REP(i, n) cerr << dist[i] << " \n"[i + 1 == n]; vector has_acorn(n, false); REP(i, k) has_acorn[d[i]] = true; vector>> child(n); auto f = [&](auto&& f, int par, int ver) -> void { for (int e : graph[ver]) { if (e == par) continue; f(f, ver, e); if (!child[e].empty()) { child[ver].emplace_back(child[e].front().first + 1, e); } else if (has_acorn[e]) { child[ver].emplace_back(1, e); } } sort(ALL(child[ver]), greater{}); }; f(f, -1, d.front()); auto g = [&](auto&& g, int par, int ver, int pd) -> void { if (par != -1) { child[ver].emplace_back(pd, par); sort(ALL(child[ver]), greater{}); } for (int e : graph[ver]) { if (e == par) continue; if (child[ver].empty()) { assert(has_acorn[ver]); g(g, ver, e, 1); } else if (child[ver].front().second == e) { if (child[ver].size() == 1) { assert(has_acorn[ver]); g(g, ver, e, 1); } else { g(g, ver, e, child[ver][1].first + 1); } } else { g(g, ver, e, child[ver].front().first + 1); } } }; g(g, -1, d.front(), 0); REP(i, n) cout << steiner + dist[i] - (child[from[i]].empty() ? 0 : child[from[i]].front().first) << '\n'; return 0; }