結果

問題 No.1718 Random Squirrel
ユーザー Kite_kuma
提出日時 2021-10-19 19:03:07
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 170 ms / 2,000 ms
コード長 24,320 bytes
コンパイル時間 2,850 ms
コンパイル使用メモリ 216,932 KB
最終ジャッジ日時 2025-01-25 01:54:43
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

/*  author:  Kite_kuma
    created: 2021.10.19 18:52:27 */
// #ifdef LOCAL
// #define _GLIBCXX_DEBUG
// #endif
#include <bits/stdc++.h>
using namespace std;
#pragma region macros
#define foa(s, v) for(auto &s : v)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define popcnt(n) __builtin_popcountll((long long)n)
#define REPname(a, b, c, d, e, ...) e
#define rep(...) REPname(__VA_ARGS__, REP3, REP2, REP1, REP0)(__VA_ARGS__)
#define REP0(x) for(int Counter_in_rep_macro = 0; Counter_in_rep_macro < (x); ++Counter_in_rep_macro)
#define REP1(i, x) for(int i = 0; i < (x); ++i)
#define REP2(i, l, r) for(int i = (l); i < (r); ++i)
#define REP3(i, l, r, c) for(int i = (l); i < (r); i += (c))
#define DREPname(a, b, c, d, e, ...) e
#define drep(...) DREPname(__VA_ARGS__, DREP3, DREP2, DREP1)(__VA_ARGS__)
#define DREP1(i, x) for(int i = (x)-1; i >= 0; --i)
#define DREP2(i, l, r) for(int i = (r)-1; i >= (l); --i)
#define DREP3(i, l, r, c) for(int i = (r)-1; i >= (l); i -= (c))
#pragma endregion
#pragma region aliases
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using vi = std::vector<int>;
using vvi = std::vector<std::vector<int>>;
using vvvi = std::vector<std::vector<std::vector<int>>>;
using vll = std::vector<ll>;
using vvll = std::vector<vll>;
using vvvll = std::vector<vvll>;
using pii = std::pair<int, int>;
using pll = std::pair<long long, long long>;
template <class T = ll>
using V = std::vector<T>;
template <class T = ll>
using VV = V<V<T>>;
template <class T = ll>
using VVV = V<V<V<T>>>;
template <class T = ll>
using pqup = std::priority_queue<T, std::vector<T>, std::greater<T>>;
template <class T = ll>
using pqdn = std::priority_queue<T>;
#pragma endregion
#pragma region constants
const int inf = 1e9;
const long long INF = 1e18;
const long double pi = acos(-1);
const char dl = '\n';
const char sp = ' ';
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const int mod_1000000007 = 1000000007;
const int mod_998244353 = 998244353;
#pragma endregion
#pragma region basic_operation
template <class T0, class T1, class T2>
inline bool in_range(T0 x, T1 lef, T2 rig) {
    return ((lef <= x) && (x < rig));
}
template <class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}
void Yes(bool f = 1) { std::cout << (f ? "Yes" : "No") << '\n'; }
void No() { std::cout << "No\n"; }
void YES(bool f = 1) { std::cout << (f ? "YES" : "NO") << '\n'; }
void NO() { std::cout << "NO\n"; }
template <class T>
void drop(T answer) {
    std::cout << answer << '\n';
    exit(0);
}
void err(bool flag = true) {
    if(!flag) return;
    std::cout << -1 << '\n';
    exit(0);
}
template <class T>
void vout(std::vector<T> const &v, bool vertically = 0) {
    if(vertically) {
        for(auto const &a : v) {
            std::cout << a << '\n';
        }
        return;
    }
    for(auto it = v.begin(); it != v.end(); it++) {
        std::cout << (*it);
        if(it != v.end() - 1) {
            std::cout << ' ';
        }
    }
    std::cout << '\n';
    return;
}
inline void print() { std::cout << '\n'; }
template <class T>
inline void print(T x) {
    std::cout << x << '\n';
    return;
}
template <typename Head, typename... Tail>
void print(Head H, Tail... T) {
    std::cout << H << " ";
    print(T...);
}
template <class T>
void add(std::vector<T> &v, T val) {
    for(auto &a : v) a += val;
    return;
}
template <class T>
T dup(T a, T b) {
    assert(b != 0);
    return (a + b - 1) / b;
}
template <class T>
T greatest_lower_multiple(T x, T d) {
    if(d == 0) return 0;
    if(d < 0) d *= -1;
    T y = x % d;
    if(y < 0) y += d;
    return x - y;
}
template <class T>
T least_upper_multiple(T x, T d) {
    return -greatest_lower_multiple(-x, d);
}
long long POW(long long a, long long n) {
    long long res = 1;
    while(n > 0) {
        if(n & 1) res = res * a;
        a = a * a;
        n >>= 1;
    }
    return res;
}
long long modpow(long long a, long long n, long long mod) {  // a^n mod
    assert(n >= 0 && mod);
    if(mod == 1) return 0LL;
    long long res = 1;
    a %= mod;
    while(n > 0) {
        if(n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res < 0 ? res + mod : res;
}
// return x which satisfies a * x % mod == gcd(a, mod)
// not (mod | a)
long long modinv(long long a, long long mod) {
    long long b = mod, u = 1, v = 0;
    while(b) {
        long long t = a / b;
        a -= t * b;
        std::swap(a, b);
        u -= t * v;
        std::swap(u, v);
    }
    u %= mod;
    if(u < 0) u += mod;
    return u;
}
template <class T>
int lb(const std::vector<T> &a, const T x) {
    return std::distance(a.begin(), std::lower_bound(a.begin(), a.end(), x));
}
template <class T>
int ub(const std::vector<T> &a, const T x) {
    return std::distance(a.begin(), std::upper_bound(a.begin(), a.end(), x));
}
template <class T>
void unq_sort(std::vector<T> &a) {
    std::sort(a.begin(), a.end());
    a.erase(std::unique(a.begin(), a.end()), a.end());
}
template <class T>
std::vector<int> press(std::vector<T> &a) {
    auto vec = a;
    unq_sort(vec);
    std::vector<int> ret;
    for(auto &v : a) ret.push_back(lb(vec, v));
    return ret;
}
#pragma endregion
#pragma region input
#define VEC(type, name, size) \
    vector<type> name(size);  \
    scanner::INPUT(name)
#define VVEC(type, name, h, w)                     \
    vector<vector<type>> name(h, vector<type>(w)); \
    scanner::INPUT(name)
#define INT(...)     \
    int __VA_ARGS__; \
    scanner::INPUT(__VA_ARGS__)
#define LL(...)            \
    long long __VA_ARGS__; \
    scanner::INPUT(__VA_ARGS__)
#define STR(...)        \
    string __VA_ARGS__; \
    scanner::INPUT(__VA_ARGS__)
#define CHR(...)      \
    char __VA_ARGS__; \
    scanner::INPUT(__VA_ARGS__)
#define DBL(...)        \
    double __VA_ARGS__; \
    scanner::INPUT(__VA_ARGS__)
#define LD(...)              \
    long double __VA_ARGS__; \
    scanner::INPUT(__VA_ARGS__)
#define TPL3(type0, type1, type2, name)   \
    std::tuple<type0, type1, type2> name; \
    scanner::INPUT(name);
#define TPL4(type0, type1, type2, type3, name)   \
    std::tuple<type0, type1, type2, type3> name; \
    scanner::INPUT(name);
namespace scanner {
template <class T>
void scan(T &a) {
    std::cin >> a;
}
template <class T, class L>
void scan(std::pair<T, L> &p) {
    scan(p.first);
    scan(p.second);
}
template <class T0, class T1, class T2>
void scan(std::tuple<T0, T1, T2> &p) {
    T0 t0;
    T1 t1;
    T2 t2;
    scan(t0);
    scan(t1);
    scan(t2);
    p = std::make_tuple(t0, t1, t2);
}
template <class T0, class T1, class T2, class T3>
void scan(std::tuple<T0, T1, T2, T3> &p) {
    T0 t0;
    T1 t1;
    T2 t2;
    T3 t3;
    scan(t0);
    scan(t1);
    scan(t2);
    scan(t3);
    p = std::make_tuple(t0, t1, t2, t3);
}
template <class T>
void scan(std::vector<T> &a) {
    for(auto &i : a) scan(i);
}
void INPUT() {}
template <class Head, class... Tail>
void INPUT(Head &head, Tail &... tail) {
    scan(head);
    INPUT(tail...);
}
}  // namespace scanner
template <typename T1, typename T2>
std::istream &operator>>(std::istream &is, std::pair<T1, T2> &p) {
    is >> p.first >> p.second;
    return is;
}
#pragma endregion
#pragma region debug
#pragma region output
template <typename T1, typename T2>
std::ostream &std::operator<<(std::ostream &os, const std::pair<T1, T2> &p) {
    os << p.first << " " << p.second;
    return os;
}
template <class T>
std::ostream &std::operator<<(std::ostream &os, const std::vector<T> &v) {
    for(int i = 0; i < (int)v.size(); i++) {
        if(i) os << " ";
        os << v[i];
    }
    return os;
}
#pragma endregion
#pragma region view
namespace viewer {
void view(const long long e) {
    if(e == INF)
        std::cerr << "INF";
    else if(e == -INF)
        std::cerr << "-INF";
    else
        std::cerr << e;
}
void view(const int e) {
    if(e == inf)
        std::cerr << "inf";
    else if(e == -inf)
        std::cerr << "-inf";
    else
        std::cerr << e;
}
template <typename T>
void view(const T e) {
    std::cerr << e;
}
template <typename T, typename U>
void view(const std::pair<T, U> &p) {
    std::cerr << "(";
    view(p.first);
    std::cerr << ", ";
    view(p.second);
    std::cerr << ")";
}
template <class T0, class T1, class T2>
void view(const std::tuple<T0, T1, T2> &p) {
    std::cerr << "(";
    view(std::get<0>(p));
    std::cerr << ", ";
    view(std::get<1>(p));
    std::cerr << ", ";
    view(std::get<2>(p));
    std::cerr << ")";
}
template <class T0, class T1, class T2, class T3>
void view(const std::tuple<T0, T1, T2, T3> &p) {
    std::cerr << "(";
    view(std::get<0>(p));
    std::cerr << ", ";
    view(std::get<1>(p));
    std::cerr << ", ";
    view(std::get<2>(p));
    std::cerr << ", ";
    view(std::get<3>(p));
    std::cerr << ")";
}
template <typename T>
void view(const std::set<T> &s) {
    if(s.empty()) {
        std::cerr << "{ }";
        return;
    }
    std::cerr << "{ ";
    for(auto &t : s) {
        view(t);
        std::cerr << ", ";
    }
    std::cerr << "\b\b }";
}
template <typename T>
void view(const std::unordered_set<T> &s) {
    if(s.empty()) {
        std::cerr << "{ }";
        return;
    }
    std::cerr << "{ ";
    for(auto &t : s) {
        view(t);
        std::cerr << ", ";
    }
    std::cerr << "\b\b }";
}
template <typename T>
void view(const std::vector<T> &v) {
    if(v.empty()) {
        std::cerr << "{ }";
        return;
    }
    std::cerr << "{ ";
    for(const auto &e : v) {
        view(e);
        std::cerr << ", ";
    }
    std::cerr << "\b\b }";
}
template <typename T>
void view(const std::vector<std::vector<T>> &vv) {
    std::cerr << "{\n";
    for(const auto &v : vv) {
        std::cerr << "\t";
        view(v);
        std::cerr << '\n';
    }
    std::cerr << "}";
}
template <typename T, typename U>
void view(const std::vector<std::pair<T, U>> &v) {
    std::cerr << "{\n";
    for(const auto &c : v) {
        std::cerr << "\t(";
        view(c.first);
        std::cerr << ", ";
        view(c.second);
        std::cerr << ")\n";
    }
    std::cerr << "}";
}
template <class T0, class T1, class T2>
void view(const std::vector<std::tuple<T0, T1, T2>> &v) {
    if(v.empty()) {
        std::cerr << "{ }";
        return;
    }
    std::cerr << '{';
    for(const auto &t : v) {
        std::cerr << "\n\t";
        view(t);
        std::cerr << ",";
    }
    std::cerr << "\n}";
}
template <class T0, class T1, class T2, class T3>
void view(const std::vector<std::tuple<T0, T1, T2, T3>> &v) {
    if(v.empty()) {
        std::cerr << "{ }";
        return;
    }
    std::cerr << '{';
    for(const auto &t : v) {
        std::cerr << "\n\t";
        view(t);
        std::cerr << ",";
    }
    std::cerr << "\n}";
}
template <typename T, typename U>
void view(const std::map<T, U> &m) {
    std::cerr << "{\n";
    for(const auto &t : m) {
        std::cerr << "\t[";
        view(t.first);
        std::cerr << "] : ";
        view(t.second);
        std::cerr << '\n';
    }
    std::cerr << "}";
}
template <typename T, typename U>
void view(const std::unordered_map<T, U> &m) {
    std::cerr << "{\n";
    for(const auto &t : m) {
        std::cerr << "\t[";
        view(t.first);
        std::cerr << "] : ";
        view(t.second);
        std::cerr << '\n';
    }
    std::cerr << "}";
}
}  // namespace viewer
#pragma endregion
// when debugging : g++ foo.cpp -DLOCAL
#ifdef LOCAL
void debug_out() {}
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    viewer::view(H);
    std::cerr << ", ";
    debug_out(T...);
}
#define debug(...)                                                \
    do {                                                          \
        std::cerr << __LINE__ << " [" << #__VA_ARGS__ << "] : ["; \
        debug_out(__VA_ARGS__);                                   \
        std::cerr << "\b\b]\n";                                   \
    } while(0)
#define dump(x)                                      \
    do {                                             \
        std::cerr << __LINE__ << " " << #x << " : "; \
        viewer::view(x);                             \
        std::cerr << '\n';                           \
    } while(0)
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif
#pragma endregion
#pragma region graph
template <class T = long long>
struct edge {
    T len;
    int from;
    int to;
    bool operator<(const edge a) const {
        if(len != a.len) return len < a.len;
        if(from != a.from) return from < a.from;
        return to < a.to;
    }
    bool operator>(const edge a) const {
        if(len != a.len) return len > a.len;
        if(from != a.from) return from > a.from;
        return to > a.to;
    }
};
template <class T = long long>
struct graph {  // 0-indexed
    T const INF = numeric_limits<T>::max() / 3;
    vector<vector<edge<T>>> edges;
    int ver;
    // constructor
    graph() = default;
    graph(int vertex) : ver(vertex), edges(vertex) {}
    //辺の追加 (0-indexed)
    void update(int from, int to, T len = 1, bool direction = 1) {  // checked
        edge<T> e;
        e.len = len;
        e.from = from;
        e.to = to;
        edges[from].push_back(e);
        if(!direction) {
            swap(e.to, e.from);
            edges[to].push_back(e);
        }
    }
    //入力受取 (1-indexed)
    void input(int edge_num, bool direction = false, bool weight = false, int index = 1) {  // checked
        for(int i = 0; i < edge_num; i++) {
            int a;
            int b;
            cin >> a >> b;
            a -= index;
            b -= index;
            T c;
            if(weight)
                cin >> c;
            else
                c = 1;
            update(a, b, c, direction);
        }
    }
    // 辺の長さを全て1とみたときの単一始点最短経路 (無理なときはINF)
    vector<T> bfs(int start) {  // checked
        // https://atcoder.jp/contests/abc007/submissions/me
        vector<T> ret(ver, INF);
        queue<int> q;
        q.push(start);
        ret[start] = 0;
        while(!q.empty()) {
            int now = q.front();
            q.pop();
            for(auto &e : edges[now]) {
                if(ret[e.to] != INF) continue;
                q.push(e.to);
                ret[e.to] = ret[now] + 1;
            }
        }
        return ret;
    }
    vector<T> zero_one_bfs(int start) {  // checked
        vector<T> ret(ver, INF);
        deque<int> deq;
        deq.push_back(start);
        ret[start] = 0;
        while(!deq.empty()) {
            int now = deq.front();
            deq.pop_front();
            for(auto &e : edges[now]) {
                if(chmin(ret[e.to], ret[now] + e.len)) {
                    if(e.len)
                        deq.push_back(e.to);
                    else
                        deq.push_front(e.to);
                }
            }
        }
        return ret;
    }
    //長さが負のpathがないときの単一始点最短経路<vll> O((ver)log(ver)+(edge))
    vector<T> dijkstra(int start) {  // checked
        // https://onlinejudge.u-aizu.ac.jp/status/users/Kite_kuma/submissions/1/GRL_1_A/judge/4817136/C++14
        vector<T> ret(ver, (T)INF);                                                   //{dist,place}
        priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> p;  //{dist,place}
        p.push({0, start});
        ret[start] = 0;
        while(!p.empty()) {
            T dist = p.top().first;
            int place = p.top().second;
            p.pop();
            if(ret[place] < dist) continue;
            for(auto &next : edges[place]) {
                int nextplace = next.to;
                T dis = next.len;
                if(ret[nextplace] > dist + dis) {
                    ret[nextplace] = dist + dis;
                    p.push({ret[nextplace], nextplace});
                }
            }
        }
        return ret;
    }
    //単一始点最短経路 O((ver)*(edge))
    //辿り着けないとき ret[i] = INF;
    //ある頂点までのコストが無限に小さくなり得るとき→ ret[i] = -INF;
    vector<T> BellmanFord(int start) {  // checked
        // https://onlinejudge.u-aizu.ac.jp/status/users/Kite_kuma/submissions/1/GRL_1_B/judge/4817139/C++14
        vector<T> ret(ver, INF);
        ret[start] = 0;
        for(int loop = 0; loop < ver - 1; loop++) {
            for(int v = 0; v < ver; v++) {
                if(ret[v] == INF) continue;
                for(auto &e : edges[v]) {
                    ret[e.to] = min(ret[e.to], ret[v] + e.len);
                }
            }
        }
        //無限降下点の検索
        queue<int> q;
        vector<bool> chk(ver, 0);
        for(int v = 0; v < ver; v++) {
            if(ret[v] == INF) continue;
            for(auto &e : edges[v]) {
                if(ret[e.to] > ret[v] + e.len) {
                    ret[e.to] = ret[v] + e.len;
                    if(!chk[e.to]) {
                        q.push(e.to);
                        chk[e.to] = 1;
                    }
                }
            }
        }
        while(!q.empty()) {
            int now = q.front();
            q.pop();
            for(auto &e : edges[now]) {
                if(!chk[e.to]) {
                    chk[e.to] = 1;
                    q.push(e.to);
                }
            }
        }
        for(int i = 0; i < ver; i++)
            if(chk[i]) ret[i] = -INF;
        return ret;
    }
    //閉路に含まれない頂点列挙
    //要素数がver未満なら閉路が存在、そうでなければ閉路は存在しない
    vector<int> topo_sort() {  // checked
        // https://onlinejudge.u-aizu.ac.jp/status/users/Kite_kuma/submissions/1/GRL_4_B/judge/4817106/C++14
        // https://onlinejudge.u-aizu.ac.jp/status/users/Kite_kuma/submissions/1/GRL_4_A/judge/4817110/C++14
        vector<int> num_input(ver);
        // 入次数
        for(int i = 0; i < ver; i++) {
            for(auto e : edges[i]) {
                num_input[e.to]++;
            }
        }
        // 入次数が0のノードをqueueで管理する
        queue<int> que;
        for(int i = 0; i < ver; i++) {
            if(num_input[i] == 0) {
                que.push(i);
            }
        }
        vector<int> ans;
        while(!que.empty()) {
            auto node = que.front();
            que.pop();
            ans.push_back(node);
            // 頂点の削除
            for(auto e : edges[node]) {
                num_input[e.to]--;
                // 行き先の入次数が0になったらqueueに追加
                if(num_input[e.to] == 0) {
                    que.push(e.to);
                }
            }
        }
        return ans;
    }
    //{{端点、端点},直径の大きさ}
    pair<pair<int, int>, T> DiameterOfTree(bool weigh = true) {  // checked
        // https://onlinejudge.u-aizu.ac.jp/status/users/Kite_kuma/submissions/1/GRL_5_A/judge/4817099/C++14
        vector<T> vec;
        vec = weigh ? dijkstra(0) : bfs(0);
        int v1 = -1;
        T dia = -1;
        for(int i = 0; i < ver; i++)
            if((dia < vec[i])) {
                dia = vec[i];
                v1 = i;
            }
        vec = weigh ? dijkstra(v1) : bfs(v1);
        dia = -1;
        int v2 = -1;
        for(int i = 0; i < ver; i++)
            if((dia < vec[i])) {
                v2 = i;
                dia = vec[i];
            }
        pair<pair<int, int>, T> ans = {{v1, v2}, dia};
        return ans;
    }
    //無向木構造を根から葉に伸びる有向木構造に書き換える
    graph<T> RootToLeaf(int root) {  // 0-indexed
        graph<T> ret(ver);
        vector<bool> chk(ver, 0);
        chk[root] = 1;
        function<void(int)> dfs = [&](int now) {
            for(auto &e : edges[now]) {
                if(chk[e.to] == 1) continue;
                chk[e.to] = 1;
                ret.update(now, e.to, e.len);
                dfs(e.to);
            }
        };
        dfs(root);
        return ret;
    }
    //無向木構造を葉から根に伸びる有向木構造に書き換える
    graph<T> LeafToRoot(int root) {  // 0-indexed
        graph<T> ret(ver);
        vector<bool> chk(ver, 0);
        chk[root] = 1;
        function<void(int)> dfs = [&](int now) {
            for(auto &e : edges[now]) {
                if(chk[e.to] == 1) continue;
                chk[e.to] = 1;
                ret.update(e.to, now, e.len);
                dfs(e.to);
            }
        };
        dfs(root);
        ret.update(root, root, 0);
        return ret;
    }
    // LeafToRootのvector版.par[i]=iの親の頂点
    vector<int> par(int root) {  // 0-indexed
        vector<int> ret(ver, -1);
        ret[root] = root;  // rootの親はroot
        function<void(int)> dfs = [&](int now) {
            for(auto &e : edges[now]) {
                if(ret[e.to] != -1) continue;
                ret[e.to] = now;
                dfs(e.to);
            }
        };
        dfs(root);
        return ret;
    }
    vector<edge<T>> ParentAndDistance(int root) {  // 0-indexed
        vector<edge<T>> ret(ver);
        for(int i = 0; i < ver; i++) ret[i].to = -1;
        ret[root].to = root;  // rootの親はroot
        ret[root].len = 0;    // rootの親との距離は0
        function<void(int)> dfs = [&](int now) {
            for(auto &e : edges[now]) {
                if(ret[e.to].to != -1) continue;
                ret[e.to].to = now;
                ret[e.to].len = e.len;
                dfs(e.to);
            }
        };
        dfs(root);
        return ret;
    }
    //隣接sheet.主にwarshall用
    vector<vector<T>> GraphArray(void) {  // chkecked
        // https://onlinejudge.u-aizu.ac.jp/status/users/Kite_kuma/submissions/1/GRL_1_C/judge/4817090/C++14
        vector<vector<T>> ret(ver, vector<T>(ver, INF));
        for(int from = 0; from < ver; from++) {
            for(auto &e : edges[from]) {
                ret[from][e.to] = e.len;
            }
            ret[from][from] = 0;
        }
        return ret;
    }
    graph<T> Prim(bool direction = 0, int start = 0) {  // checked
        // https://onlinejudge.u-aizu.ac.jp/status/users/Kite_kuma/submissions/1/GRL_2_A/judge/4817129/C++14
        graph<T> ret(ver);
        priority_queue<edge<T>, vector<edge<T>>, greater<edge<T>>> p;
        for(auto &e : edges[start]) {
            p.push(e);
        }
        vector<bool> chk(ver, 0);
        chk[start] = 1;
        while(!p.empty()) {
            auto ed = p.top();
            p.pop();
            if(chk[ed.to]) continue;
            chk[ed.to] = 1;
            ret.update(ed.from, ed.to, ed.len, direction);
            for(auto &e : edges[ed.to]) {
                p.push(e);
            }
        }
        return ret;
    }
    //各頂点を根としたときの木の高さ
    vector<T> height(int start = 0) {  // checked
        // https://onlinejudge.u-aizu.ac.jp/status/users/Kite_kuma/submissions/1/GRL_5_B/judge/4817082/C++14
        vector<T> fir(ver, -1), sec(ver, -1);
        function<T(int, int)> dfs = [&](int now, int par) {
            T f = 0, s = 0;  // startを根としたときのnowからの深さ1番目、2番目
            for(auto &e : edges[now]) {
                if(e.to == par) continue;
                s = max(s, dfs(e.to, now) + e.len);
                if(f < s) swap(f, s);
            }
            sec[now] = s;
            return fir[now] = f;
        };
        dfs(start, -1);
        function<void(int, int, T, T, T)> sol = [&](int now, int par, T parf, T pars, T parlen) {
            if(fir[now] + parlen == parf) parf = pars;
            sec[now] = max(sec[now], parf + parlen);
            if(fir[now] < sec[now]) swap(fir[now], sec[now]);
            for(auto &e : edges[now]) {
                if(e.to == par) continue;
                sol(e.to, now, fir[now], sec[now], e.len);
            }
            return;
        };
        sol(start, -1, -1, -1, -1);
        return fir;
    }
    //全方位木DP
    //マージ関数、上に送るための関数、単位元、はじめの根
    // 関数はstd::functionで渡す
    template <class U>
    vector<U> ReRootingDP(U &unit, function<U(U, U)> &merge, function<U(int, U, T)> &send, int root = 0) {
        auto tr = RootToLeaf(root);
        vector<vector<U>> v(ver);
        vector<U> ret(ver);  //求める答
        function<U(int)> treeDP = [&](int now) {
            U res = unit;
            vector<U> vec;
            for(auto &e : tr.edges[now]) {
                U u = send(e.to, treeDP(e.to), e.len);
                v[now].push_back(u);
                res = merge(res, u);
            }
            return res;
        };
        treeDP(root);
        function<void(int, U, int, T)> rerooting = [&](int now, U ans_par, int par, T len) {
            if(now != root) ans_par = send(par, ans_par, len);
            int sz = v[now].size();
            vector<U> data_front(sz + 1), data_back(sz + 1);
            data_front[0] = data_back[sz] = unit;
            for(int i = 0; i < sz; i++) {
                data_front[i + 1] = merge(data_front[i], v[now][i]);
                data_back[sz - i - 1] = merge(v[now][sz - i - 1], data_back[sz - i]);
            }
            for(int i = 0; i < sz; i++) {
                auto nxtans = merge(ans_par, merge(data_front[i], data_back[i + 1]));
                rerooting(tr.edges[now][i].to, nxtans, now, tr.edges[now][i].len);
            }
            ret[now] = merge(ans_par, data_front[sz]);
            return;
        };
        rerooting(root, unit, root, 0);
        return ret;
    }
    // HL分解
};
// 強連結成分分解
struct SCC {
    graph<int> ng, rg;  // normal graph, reversed graph
    vector<int> compo;  // compo[i] = 新グラフでiが属する頂点集合番号
    vector<int> order;
    vector<bool> used;
    graph<int> ret;
    // g:元のグラフ, ret:強連結成分分解後のグラフ
    template <class T>
    SCC(graph<T> &g) : ng(g.ver), rg(g.ver), compo(g.ver, -1), used(g.ver, false) {
        for(int from = 0; from < g.ver; from++) {
            for(auto &e : g.edges[from]) {
                ng.update(e.from, e.to, 1, 1);
                rg.update(e.to, e.from, 1, 1);
            }
        }
        for(int i = 0; i < ng.ver; i++) dfs(i);
        reverse(order.begin(), order.end());
        int group = 0;
        for(auto i : order)
            if(compo[i] == -1) rdfs(i, group), group++;
        ret.edges.resize(group);
        for(int i = 0; i < g.ver; i++) {
            for(auto &e : g.edges[i]) {
                int s = compo[i], t = compo[e.to];
                if(s != t) ret.update(s, t, 1, 1);
            }
        }
    }
    int operator[](int k) { return compo[k]; }
    void dfs(int now) {
        if(used[now]) return;
        used[now] = true;
        for(auto &e : ng.edges[now]) dfs(e.to);
        order.push_back(now);
    }
    void rdfs(int now, int count) {
        if(compo[now] != -1) return;
        compo[now] = count;
        for(auto &e : rg.edges[now]) rdfs(e.to, count);
    }
};
#pragma endregion
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout << std::fixed << std::setprecision(15);
    srand((unsigned)time(NULL));
    int n, k;
    cin >> n >> k;
    graph<> g(n);
    g.input(n - 1, false, false, 1);
    vi donguri(n);
    rep(i, k) {
        int d;
        cin >> d;
        donguri[--d]++;
    }
    function<pair<ll, ll>(pair<ll, ll>, pair<ll, ll>)> merge = [](pair<ll, ll> a, pair<ll, ll> b) {
        return (pair<ll, ll>){min(a.second + b.first, a.first + b.second), a.second + b.second};
    };
    function<pair<ll, ll>(int, pair<ll, ll>, ll)> send = [&](int id, pair<ll, ll> predata, ll len) {
        if(predata == make_pair(0LL, 0LL) && !donguri[id]) return predata;
        return pair(predata.first + 1, predata.second + 2);
    };
    pair<ll, ll> unit(0, 0);
    vector<pair<ll, ll>> res = g.ReRootingDP(unit, merge, send);
    rep(i, n) { cout << res[i].first << dl; }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0