题解 P7443 【「EZEC-7」加边】

· · 题解

可以考虑先 DP 一遍求出在不加边的情况下，每个节点是必胜态还是必败态。

首先显然在根节点与 Alice 的先后手操作状态相符合时根本不需要加边。

然后需要证明一个结论：加的这一条边，一定不会是一条回边。

证明也很简单，因为如果是回边的话，那么在这条加入的边起点上，如果是必胜态，那么当前操作者一定不会进入回边，如果是必败态，当前操作者一定会选择走向回边，然后构成循环。

因此，加入回边，要么不会影响结果，要么会使得操作过程陷入死循环。

如何修改一个点的状态？

考虑加边的影响，加这条边只可能将一个必败点转变为必胜点。

将一个必败节点转为必胜态，只需要其中一个节点转变为必败态，或者加一条边连接一个合法的必败态节点即可。

将一个必胜节点转为必败节点。一个必胜节点能被改为必败节点，当且仅当其子节点只有一个必败节点，修改的代价为将这个必败子节点转变为必胜点的代价。

那么，在遍历的时候，可以对于必胜节点，处理一下这个节点是否只有一个必败子节点以及这个子节点的编号。

对于必败节点，则只需对所有子节点代价取最小值，然后再与直接加边取个最小值即可。

如何求直接加边的代价

发现题目中的式子，对于固定的起点，a 的值和系数都是固定的，所以要取的点一定是 b 值最小的满足条件的必败态节点。

这个可以用线段树实现。每次将在搜索栈中的节点标记为不可抵达（即将线段树对应位置上的权值标记为无穷大）访问完毕时再单点修改回来即可。查询时访问全局最小值。

线段树常数太大？被卡成 90pts。因为只需要单点修改，查询全局最值，那就用 zkw 树。复杂度带 \log 但是常数很小，可以通过。

Ex：这个步骤一种线性实现的方式

遍历时对每个节点处理出以该节点为根的最小值，以及每个点所有出点按遍历顺序的前后缀最小值。

第二次遍历的时候进入下一层子节点的时将 当前节点的答案 与即将进入节点遍历顺序 \pm 1 位置的 前/后缀最小值 取个最小值即可。

对当前节点查询的时候取的点为 当前节点的答案 与 所有子节点的子树的最小值 的最小值。

这段话说的好乱啊，希望断句有点帮助吧。

代码：

只有用了 zkw 树的。

#include <bits/stdc++.h>

#define LL __int128

using namespace std;

template <typename Temp> inline void read(Temp & res) {
    Temp fh = 1; res = 0; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') fh = -1;
    for(; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ '0');
    res = res * fh;
}
template <typename Temp> inline void Checkmin(Temp & num, Temp comp) {
    if(comp < num) num = comp;
}

const int Maxn = 2e5 + 5;
const LL INF = 0x7fffffffffffffff / 2;

struct e {
    int to, nxt;
} b[Maxn];
int head[Maxn], ecnt;
void add(int u, int v) {b[++ecnt] = (e) {v, head[u]}; head[u] = ecnt;}

bool g[Maxn], h[Maxn]; LL f[Maxn];

int n, w, x, L;
LL A, B, a[Maxn];

#define ls t << 1
#define rs t << 1 | 1
LL data[Maxn << 2];
void modify(int pos, LL d) {
    pos += L; data[pos] = d;
    while(pos >>= 1) data[pos] = min(data[pos << 1], data[pos << 1 | 1]);
}
#undef ls
#undef rs

void dfs1(int t) {
    int cnt = 0;
    for(int i = head[t]; i; i = b[i].nxt) {
        dfs1(b[i].to);
        if(!g[b[i].to]) cnt++;
    }
    if(cnt == 0) g[t] = 0, h[t] = 0;
    else g[t] = 1, h[t] = (cnt == 1);
    return;
}

void dfs2(int t) {
    if(g[t] == 0) modify(t, INF);
    for(int i = head[t]; i; i = b[i].nxt) {
        dfs2(b[i].to);
        if(!g[t]) Checkmin(f[t], f[b[i].to]);
        else if(h[t]) {
            if(!g[b[i].to]) f[t] = f[b[i].to];
        }
    }
    if(!g[t]) Checkmin(f[t], A * a[t] + B * data[1]);
    if(g[t] == 0) modify(t, a[t]);
}

inline void Main() {
    read(n); read(w); read(A); read(B); ecnt = 0; L = 1; while(L <= n) L <<= 1;
    for(int i = 1; i <= n; ++i) head[i] = 0, f[i] = INF;
    for(int i = 1; i <= (n << 2); ++i) data[i] = INF;
    for(int i = 2; i <= n; ++i) read(x), add(x, i);
    for(int i = 1; i <= n; ++i) read(a[i]);
    dfs1(1);
    if((w == 0 && g[1]) || (w == 1 && (!g[1]))) {printf("0\n"); return;}
    for(int i = 1; i <= n; ++i) if(!g[i]) modify(i, a[i]);
    dfs2(1);
    printf("%lld\n", (f[1] != INF ? f[1] : -1));
    return;
}

int main() {
    int T; read(T);
    while(T--) Main();
    return 0;
}