#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #pragma warning(disable:4996) #define ATCODER #ifdef ATCODER #include #endif typedef long long ll; typedef unsigned long long ull; #define LINF 9223300000000000000 #define LINF2 1223300000000000000 #define LINF3 1000000000000 #define INF 2140000000 //const long long MOD = 1000000007; const long long MOD = 998244353; using namespace std; #ifdef ATCODER using namespace atcoder; #endif // // 全方位木 // ST:各nodeに対する部分木に関する情報。単位元も定義する // op:(ST,ST)→ST という関数を定義。各部分木の情報を寄せ集めるときに使う // op2:ST→ST 子の部分木を合成した後、そこからcurrentの部分木の情報を計算。 // 出力 // vector vans: 各nodeについて、そこから全方向への部分木の情報を寄せ集めたもの // vector flag; struct ST { ST() { dist[0] = dist[1] = 0; // unit item } int dist[2]; // 0:go & back 1:go }; ST op(const ST a, const ST b) { ST c; c.dist[0] = a.dist[0] + b.dist[0]; c.dist[1] = min(a.dist[1] + b.dist[0], a.dist[0] + b.dist[1]); return c; } ST op2(const ST a, int f) { ST b = a; if (b.dist[1]) { b.dist[0] += 2; b.dist[1] += 1; } else if( f ) { b.dist[0] = 2; b.dist[1] = 1; } return b; } void dfs0(const vector>& g, int par, int curr, vector& vs0) { ST st; int found = 0; for (int i = 0; i < (int)g[curr].size(); i++) { int ne = g[curr][i]; if (par == ne) continue; dfs0(g, curr, ne, vs0); st = op(st, vs0[ne]); } vs0[curr] = op2(st, flag[curr]); return; } void dfs1(const vector>& g, int par, int curr, const vector& vs0, const ST st1, vector& vans) { vector v; for (int i = 0; i < (int)g[curr].size(); i++) { int ne = g[curr][i]; if (par == ne) continue; v.push_back(ne); } int num = (int)v.size(); vector sv0(num + 1), sv1(num + 1); for (int i = 0; i < num; i++) { sv0[i + 1] = op(sv0[i], vs0[v[i]]); } for (int i = num-1; i >= 0; i--) { sv1[i] = op(sv1[i+1], vs0[v[i]]); } for (int i = 0; i < num; i++) { int ne = v[i]; ST st2 = op(sv0[i], sv1[i + 1]); ST st3 = op(st1, st2); ST st = op2(st3, flag[curr]); dfs1(g, curr, ne, vs0, st, vans); } vans[curr] = op(st1, sv0[num]); return; } vector reroot(const vector>& g) { int n = (int)g.size(); vector vs0(n), vans(n); dfs0(g, -1, 0, vs0); ST st; dfs1(g, -1, 0, vs0, st, vans); return vans; } void solve() { int n, K; scanf("%d%d", &n, &K); flag.resize(n); vector> g(n); // to for (int i = 0; i < n - 1; i++) { int a, b; scanf("%d%d", &a, &b); a--; b--; g[a].push_back(b); g[b].push_back(a); } for (int i = 0; i < K; i++) { int t; scanf("%d", &t); t--; flag[t] = 1; } vector vans = reroot(g); for (int i = 0; i < n; i++) { printf("%d\n", vans[i].dist[1]); } return; } int main() { #if 1 solve(); #else int T, t; scanf("%d", &T); for (t = 0; t < T; t++) { //printf("Case #%d: ", t + 1); solve(); } #endif return 0; }