<虚树+树型DP> HNOI2014世界树

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

typedef long long LL;

const int MAXN = 3e5 + 10;

inline int in()

{

    int x = 0, flag = 1; char ch = getchar();

    while (ch < '0' || ch > '9') { if (ch == '-') flag = -1; ch = getchar(); }

    while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();

    return x * flag;

}

int n, m, q;

struct Gra

{

    int head[MAXN], nume;

    struct Adj { int nex, to; } adj[MAXN << 1];

    void clear()

        {

            memset(head, 0, sizeof head);

            nume = 0;

        }

    void addedge(int from, int to)

        {

            adj[++nume] = (Adj) { head[from], to };

            head[from] = nume;

        }

    void link(int from, int to)

        {

            addedge(from, to);

            addedge(to, from);

        }

} g1, g2;

int lg[MAXN], up[20][MAXN], dfn[MAXN], ind, dep[MAXN], size[MAXN];

void DFS(int u)

{

    dfn[u] = ++ind;

    dep[u] = dep[up[0][u]] + 1;

    size[u] = 1;

    for (int i = 1; (1 << i) <= dep[u]; ++ i)

        up[i][u] = up[i - 1][up[i - 1][u]];

    for (int i = g1.head[u]; i; i = g1.adj[i].nex)

    {

        int v = g1.adj[i].to;

        if (v == up[0][u]) continue;

        up[0][v] = u;

        DFS(v);

        size[u] += size[v];

    }

}

int lca(int x, int y)

{

    if (dep[x] > dep[y]) swap(x, y);

    while (dep[x] != dep[y]) y = up[lg[dep[y] - dep[x]]][y];

    if (x == y) return x;

    for (int i = lg[dep[x]]; i >= 0; -- i)

        if (up[i][x] != up[i][y]) x = up[i][x], y = up[i][y];

    return up[0][x];

}

int a[MAXN], id[MAXN], ans[MAXN];

bool cmpd(int x, int y) { return dfn[x] < dfn[y]; }

int stk[MAXN], top;

bool iskey[MAXN];

void insert(int x)

{

    if (x == stk[1]) return;

    int LCA = lca(x, stk[top]);

    if (LCA == stk[top]) return (void)(stk[++top] = x);

    while (top > 1 && dep[LCA] <= dep[stk[top - 1]])

    {

        g2.addedge(stk[top - 1], stk[top]);

        -- top;

    }

    if (LCA != stk[top]) g2.addedge(LCA, stk[top]), stk[top] = LCA;

    stk[++top] = x;

}

struct Mn

{

    int id, v;

} mn[MAXN];

void getmin(int x, int y)

{

    int val = mn[y].v + abs(dep[x] - dep[y]);

    if (val < mn[x].v)

        mn[x] = (Mn) { mn[y].id, val };

    else if (val == mn[x].v && mn[y].id < mn[x].id)

        mn[x].id = mn[y].id;

}

void DFS1(int u)

{

    if (iskey[u]) mn[u] = (Mn) { u, 0 };

    else mn[u] = (Mn) { 300001, 2333333 };

    for (int i = g2.head[u]; i; i = g2.adj[i].nex)

    {

        int v = g2.adj[i].to;

        DFS1(v);

        getmin(u, v);

    }

    return ;

}

int jump(int x, int d)

{

    for (int i = 19; i >= 0; -- i)

        if ((1 << i) <= d) x = up[i][x], d -= (1 << i);

    return x;

}

void DFS2(int u)

{

    ans[mn[u].id] += 1;

    int sum = 0;

    for (int i = g2.head[u]; i; i = g2.adj[i].nex)

    {

        int v = g2.adj[i].to;

        getmin(v, u);

        int dis = dep[v] - dep[u], mid = (mn[u].v + mn[v].v + dis) / 2;

        int uson = jump(v, dis - 1);

        sum += size[uson];

        if (mid - mn[v].v > 0 && mid - mn[v].v < dis)

        {

            int mi = jump(v, mid - mn[v].v), mison = jump(v, mid - mn[v].v - 1);

            ans[mn[v].id] += size[mison] - size[v];

            ans[mn[u].id] += size[uson] - size[mi];

            if (mid * 2 != mn[u].v + mn[v].v + dis) ans[mn[v].id] += size[mi] - size[mison];

            else

            {

                if (mn[u].id < mn[v].id) ans[mn[u].id] += size[mi] - size[mison];

                else ans[mn[v].id] += size[mi] - size[mison];

            }

        }

        else if (mid - mn[v].v <= 0) ans[mn[u].id] += size[uson] - size[v];

        else if (mid - mn[v].v >= dis) ans[mn[v].id] += size[uson] - size[v];

        DFS2(v);

    }

    ans[mn[u].id] += size[u] - sum - 1;

    g2.head[u] = 0;

    iskey[u] = false;

    return ;

}

int main()

{

    g1.clear(); g2.clear();

    n = in();

    for (int i = 1; i <= n; ++ i)

        lg[i] = lg[i - 1] + ((2 << lg[i - 1]) == i);

    for (int i = 1; i < n; ++ i)

    {

        int u = in(), v = in();

        g1.link(u, v);

    }

    DFS(1);

    q = in();

    while (q --)

    {

        m = in();

        g2.nume = 0;

        for (int i = 1; i <= m; ++ i) a[i] = in(), id[i] = a[i];

        sort(a + 1, a + m + 1, cmpd);

        top = 0; stk[++ top] = 1;

        for (int i = 1; i <= m; ++ i) insert(a[i]), iskey[a[i]] = true;

        while (top > 1) g2.addedge(stk[top - 1], stk[top]), -- top;

        DFS1(1);

        DFS2(1);

        for (int i = 1; i <= m; ++ i) printf("%d ", ans[id[i]]); puts("");

        for (int i = 1; i <= m; ++ i) ans[id[i]] = 0;

    }

    return 0;

}
巴特西

<虚树+树型DP> HNOI2014世界树

<虚树+树型DP> HNOI2014世界树

最新文章

热门文章
