某岛

… : "…アッカリ~ン . .. . " .. .
March 14, 2020

Codeforces Round #328 (Div. 2)

虚树求直径。

const int N = int(1e6) + 9, LV = 21;

VI adj[N]; int dfn[N], lfn[N], dep[N];
int tt;

int n,m,cnt,ind,top;
int fa[N][LV];

bool cmp(int a,int b) {
    return dfn[a]<dfn[b];
}
void dfs(int u) {
    dfn[u] = ++tt;
    ECH(it, adj[u]) {
        int v = *it;
        if (v == fa[u][0]) continue;
        fa[v][0] = u; for (int lv=0;fa[v][lv+1]=fa[fa[v][lv]][lv];++lv);
        dep[v] = dep[u] + 1;
        dfs(v);
    }
    lfn[u] = tt;
}
inline int move_up(int x, int t){
    for (int lv=0;t;++lv,t>>=1)
        if (t&1) x = fa[x][lv];
    return x;
}
inline int move_to(int x, int t){
    return move_up(x, dep[x]-t);
}
inline int lca(int x, int y) {
    if (dep[x]>dep[y]) swap(x,y); y=move_to(y, dep[x]); if (x==y) return x;
    DWN(lv, LV, 0) if (fa[x][lv]!=fa[y][lv]) x = fa[x][lv], y = fa[y][lv];
    return fa[x][0];
}
inline int dist(int x, int y) {
    return dep[x] + dep[y] - 2*dep[lca(x,y)];
}

namespace Virtual_Tree {
    VI adj[N]; int sta[N], top; bool bj[N];
    int total; PII f[N], diameter;

    void dfs(int u) {
        f[u] = {0, bj[u] ? -u : 0};
        for (auto v: adj[u]) {
            dfs(v); int w = dep[v] - dep[u]; f[v].fi += w;
            checkMax(diameter, {f[u].fi + f[v].fi, max(f[u].se, f[v].se)});
            checkMax(f[u], f[v]); total += w;
        }
        checkMax(diameter, f[u]);
    }

    void gao() {
        VI T; DO(m) {
            int x; RD(x); bj[x] = 1;
            T.PB(x);
        }
        UNQ(T, cmp); DWN(i, SZ(T)-1, 0) {
            int z = lca(T[i], T[i+1]);
            T.PB(z);
        }
        UNQ(T, cmp); top = 0; REP(i, SZ(T)) {
            int u = T[i];
            while (top && lfn[sta[top]] < dfn[u]) --top;
            if (top) adj[sta[top]].PB(u);
            sta[++top] = u;
        }

        total = 0; diameter = {-INF, 0}; dfs(T[0]);
        printf("%d\n", -diameter.se);
        printf("%d\n", 2*total-diameter.fi);
    }
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    RD(n, m); DO(n-1) {
        int x, y; RD(x, y);
        adj[x].PB(y);
        adj[y].PB(x);
    }
    dfs(1); Virtual_Tree::gao();
}