[虚树模板] 洛谷P2495 消耗战

[update]

好像有个东西叫笛卡尔树，好像是这样建的.....

inline void build_d() {
    stk[top = 1] = 1;
    for(int i = 2; i <= n; i++) {
        while(top && val[stk[top]] <= val[i]) {
            ls[i] = stk[top];
            top--;
        }
        if(ls[i]) {
            fa[ls[i]] = i;
        }
        if(top) {
            fa[i] = stk[top];
            rs[stk[top]] = i;
        }
        stk[++top] = i;
    }
    RT = stk[1];
    return;
}

题意：给定树上k个点，求切断这些点到根路径的最小代价。∑k <= 5e5

解：虚树。

构建虚树大概是这样的：设加入点与栈顶的lca为y，比较y和栈中第二个元素的DFS序大小关系。

代码如下：

inline bool cmp(const int &a, const int &b) {
    return pos[a] < pos[b];
}

inline void build_t() {
    std::sort(imp + 1, imp + k + 1, cmp);
    TP = top = 0;
    stk[++top] = imp[1];
    use[imp[1]] = Time;
    E[imp[1]] = 0;
    for(int i = 2; i <= k; i++) {
        int x = imp[i], y = lca(x, stk[top]);
        if(use[x] != Time) {
            use[x] = Time;
            E[x] = 0;
        }
        if(use[y] != Time) {
            use[y] = Time;
            E[y] = 0;
        }
        while(top > 1 && pos[y] <= pos[stk[top - 1]]) {
            ADD(stk[top - 1], stk[top]);
            top--;
        }
        if(stk[top] != y) {
            ADD(y, stk[top]);
            stk[top] = y;
        }
        stk[++top] = x;
    }
    while(top > 1) {
        ADD(stk[top - 1], stk[top]);
        top--;
    }
    RT = stk[top];
    return;
}

然后本题建虚树跑DP就行了。注意虚树根节点的DP初值和虚树的边权。

#include <cstdio>
#include <algorithm>

typedef long long LL;
const int N = 250010;
const LL INF = 1e18;

struct Edge {
    int nex, v;
    LL len;
}edge[N << 1], EDGE[N << 1]; int tp, TP;

int e[N], siz[N], stk[N], top, Time, n, fa[N][20], k, RT, num, pos[N], pw[N], now[N], imp[N], E[N], d[N], use[N];
LL f[N], small[N][20];

inline void ADD(int x, int y, LL z) {
    TP++;
    EDGE[TP].v = y;
    EDGE[TP].len = z;
    EDGE[TP].nex = E[x];
    E[x] = TP;
    return;
}

inline void add(int x, int y, LL z) {
    top++;
    edge[top].v = y;
    edge[top].len = z;
    edge[top].nex = e[x];
    e[x] = top;
    return;
}

void DFS_1(int x, int father) { // get fa small
    fa[x][0] = father;
    d[x] = d[father] + 1;
    pos[x] = ++num;
    for(int i = e[x]; i; i = edge[i].nex) {
        int y = edge[i].v;
        if(y == father) {
            continue;
        }
        small[y][0] = edge[i].len;
        DFS_1(y, x);
    }
    return;
}

inline int lca(int x, int y) {
    if(d[x] > d[y]) {
        std::swap(x, y);
    }
    int t = pw[n];
    while(t >= 0 && d[x] < d[y]) {
        if(d[fa[y][t]] >= d[x]) {
            y = fa[y][t];
        }
        t--;
    }
    if(x == y) {
        return x;
    }
    t = pw[n];
    while(t >= 0 && fa[x][0] != fa[y][0]) {
        if(fa[x][t] != fa[y][t]) {
            x = fa[x][t];
            y = fa[y][t];
        }
        t--;
    }
    return fa[x][0];
}

inline bool cmp(const int &a, const int &b) {
    return pos[a] < pos[b];
}

inline LL getMin(int x, int y) {
    LL ans = INF;
    int t = pw[d[y] - d[x]];
    while(t >= 0 && y != x) {
        if(d[fa[y][t]] >= d[x]) {
            ans = std::min(ans, small[y][t]);
            y = fa[y][t];
        }
        t--;
    }
    return ans;
}

inline void build_t() {
    std::sort(imp + 1, imp + k + 1, cmp);
    TP = top = 0;
    stk[++top] = imp[1];
    use[imp[1]] = Time;
    E[imp[1]] = 0;
    for(int i = 2; i <= k; i++) {
        int x = imp[i], y = lca(x, stk[top]);
        if(use[x] != Time) {
            use[x] = Time;
            E[x] = 0;
        }
        if(use[y] != Time) {
            use[y] = Time;
            E[y] = 0;
        }
        while(top > 1 && pos[y] <= pos[stk[top - 1]]) {
            ADD(stk[top - 1], stk[top], getMin(stk[top - 1], stk[top]));
            top--;
        }
        if(stk[top] != y) {
            ADD(y, stk[top], getMin(y, stk[top]));
            stk[top] = y;
        }
        stk[++top] = x;
    }
    while(top > 1) {
        ADD(stk[top - 1], stk[top], getMin(stk[top - 1], stk[top]));
        top--;
    }
    RT = stk[top];
    return;
}

void DFS(int x) {
    siz[x] = (now[x] == Time);
    LL temp = 0;
    for(int i = E[x]; i; i = EDGE[i].nex) {
        int y = EDGE[i].v;
        f[y] = EDGE[i].len;
        DFS(y);
        siz[x] += siz[y];
        if(siz[y]) {
            temp += f[y];
        }
    }
    if(now[x] != Time) {
        f[x] = std::min(f[x], temp);
    }
    return;
}

void out(int x) {
    return;
}

int main() {
    scanf("%d", &n);
    /*if(n > 100) {
        return -1;
    }*/
    int x, y; LL z;
    for(int i = 1; i < n; i++) {
        scanf("%d%d%lld", &x, &y, &z);
        add(x, y, z);
        add(y, x, z);
    }
    // get lca min_edge
    DFS_1(1, 0);
    for(int i = 2; i <= n; i++) {
        pw[i] = pw[i >> 1] + 1;
    }
    for(int j = 1; j <= pw[n]; j++) {
        for(int i = 1; i <= n; i++) {
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
            small[i][j] = std::min(small[i][j - 1], small[fa[i][j - 1]][j - 1]);
        }
    }

    int m;
    scanf("%d", &m);
    for(Time = 1; Time <= m; Time++) {
        scanf("%d", &k);
        //printf("
 k = %d 
", k);
        for(int i = 1; i <= k; i++) {
            scanf("%d", &imp[i]);
            now[imp[i]] = Time;
        }
        //printf("input over 
");
        build_t();
        //out(RT);
        f[RT] = getMin(1, RT);
        DFS(RT);
        printf("%lld
", f[RT]);
    }

    return 0;
}