出于能恢复的特性 , 炸掉一个点会使某个中枢结点断电的case只可能是以 $1$ 为源点的所有支配点。

所以求出支配树然后在上面 dp 就好了。

30分就是给 DAG 上求支配树的，比较好写吧。

30pts:

$on DAG, \mathcal{O(n \log n + m)}$ .

#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define rii(x,y) ri(x), ri(y)
#define ri3(x,y,z) ri(x), ri(y), ri(z)
#define rz resize
#define pb push_back

using namespace std;

typedef vector<int> VI;
typedef long long ll;
typedef long double ldb;
typedef double db;

inline void ri(int &x) {
    x = 0; char ch; int f = 1;
    do { ch = getchar(); if(ch == '-') f = -1; } while( ch < '0' || ch > '9' );
    do { x = (x<<3) + (x<<1) + (ch&15), ch = getchar(); } while( ch >= '0' && ch <= '9' );
    x *= f;
}

VI ind, dep;
vector< VI > G, _G, DOM;

queue<int> q;
vector< VI > fa;

int lca(int u, int v) {
    if(dep[u] < dep[v]) swap(u, v);
    for(int i = 19; ~i; --i) if(dep[fa[u][i]] >= dep[v]) u = fa[u][i];
    if(u == v) return u;
    for(int i = 19; ~i; --i) if(fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
    return fa[u][0];
}

void topo() {
    q.push(1);
    while(!q.empty()) {
        int cur = q.front(); q.pop();
        int pre = 0;
        if(_G[cur].size()) {
            pre = _G[cur][0];
            for(int i = 1; i < _G[cur].size(); ++i) pre = lca(pre, _G[cur][i]);
        }
        fa[cur][0] = pre; dep[cur] = dep[pre] + 1;
        DOM[pre].pb(cur);
        for(int i = 1; i < 20; ++i) fa[cur][i] = fa[fa[cur][i-1]][i-1];
        for(int ver : G[cur]) if(--ind[ver] == 0) q.push(ver);
    }
}

VI vital, f, pt;
void dfs(int cur) {
    f[cur] = 0;
    for(int ver : DOM[cur]) {
        dfs(ver); f[cur] += f[ver];
    }
    f[cur] = pt[cur] ? vital[cur] : min(vital[cur], f[cur]);
}

int main() {
    int n, m, q, u, v;
    ri3(n, m, q);
    vital.rz(n + 1); ind.rz(n + 1); fa.rz(n + 1); dep.rz(n + 1);
    G.rz(n + 1); _G.rz(n + 1); pt.rz(n + 1); DOM.rz(n + 1); f.rz(n + 1);

    rep(i,0,n) fa[i].rz(20);
    rep(i,2,n) ri(vital[i]); vital[1] = 2e9+7;

    rep(i,1,m) {
        rii(u, v);
        G[u].pb(v);
        _G[v].pb(u);
        ++ind[v];
    }

    rep(qr,1,q) { ri(u); pt[u] = 1;}
    topo();
    dfs(1);
    printf("%d\n", f[1]);
    return 0;
}

100pts:

$\mathcal{O((n+m)\alpha(n))}$ .

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <iostream>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define per(i,a,b) for(int i=a;i>=(b);--i)
#define repp(i,a,b) for(int i=a;i<(b);++i)
#define perr(i,a,b) for(int i=a;i>(b);--i)
#define pb push_back
#define rz resize
#define VI vector<int>
#define rii(x,y) ri(x), ri(y)
#define ri3(x,y,z) ri(x), ri(y), ri(z)

using namespace std;

inline void ri(int &x) {
    x = 0; char ch; int f = 1;
    do { ch = getchar(); if(ch == '-') f = -1; } while( ch < '0' || ch > '9' );
    do { x = (x<<3) + (x<<1) + (ch&15), ch = getchar(); } while( ch >= '0' && ch <= '9' );
    x *= f;
}

vector< VI > G, _G, DOM;
VI dfn, idfn, fa;
int dfs_clock = 1;

inline int minpt(int u, int v) {
    return dfn[u] < dfn[v] ? u : v;
}

VI par, dat, sdom, idom;
vector< VI > buc;

void dfs(int pre, int cur) {
    idfn[dfs_clock] = cur; dfn[cur] = dfs_clock++;
    fa[cur] = pre;
    for(int ver : G[cur]) if(!dfn[ver]) dfs(cur, ver);
}

int find(int x) {
    if(par[x] == x) return x;
    int p = find(par[x]);
    if(dfn[sdom[dat[x]]] > dfn[sdom[dat[par[x]]]]) dat[x] = dat[par[x]];
    return par[x] = p;
}

int eval(int x) { find(x); return dat[x]; }

void lengauer_tarjan(int n, int r) {
    dfs_clock = 1;
    dfs(0, r);
    --dfs_clock;
    for(int i = 1; i <= n; ++i) par[i] = dat[i] = sdom[i] = i;
    for(int i = n; i > 1; --i) {
        int cur = idfn[i];
        for(int ver : _G[cur]) {
            if(!dfn[ver]) continue;
            int ev = eval(ver);
            if(dfn[sdom[cur]] > dfn[sdom[ev]]) sdom[cur] = sdom[ev];
        }
        buc[sdom[cur]].pb(cur); par[cur] = fa[cur];
        for(int ver : buc[fa[cur]]) {
            int ev = eval(ver);
            if(sdom[ev] == fa[cur]) idom[ver] = fa[cur];
            else idom[ver] = ev;
        }
        buc[fa[cur]].clear();
    }
    for(int i = 2; i <= dfs_clock; ++i) {
        int cur = idfn[i];
        if(idom[cur] != sdom[cur]) idom[cur] = idom[idom[cur]];
        DOM[idom[cur]].pb(cur);
    }
    idom[r] = 0;
}


VI vital, pt;
VI f;
void work(int cur) {
    f[cur] = 0;
    for(int ver : DOM[cur]) {
        work(ver);
        f[cur] += f[ver];
    }
    f[cur] = pt[cur] ? vital[cur] : min(f[cur], vital[cur]);
}

int main() {
    if(fopen("yl.in", "r")) {
        freopen("yl.in", "r", stdin);
        freopen("yl.out", "w", stdout);
    }
    int n, m, q, u, v;
    ri3(n, m, q);
    G.rz(n + 1); _G.rz(n + 1); DOM.rz(n + 1); dfn.rz(n + 1); idfn.rz(n + 1); fa.rz(n + 1); par.rz(n + 1); dat.rz(n + 1); sdom.rz(n + 1); idom.rz(n + 1); buc.rz(n + 1); vital.rz(n + 1); pt.rz(n + 1); f.rz(n + 1);
    rep(i,2,n) ri(vital[i]); vital[1] = 2e9 + 7;
    while(m--) {
        rii(u, v);
        G[u].pb(v);
        _G[v].pb(u);
    }
    lengauer_tarjan(n, 1);
    rep(i,1,q) {
        ri(u); pt[u] = 1;
    }
    work(1);
    printf("%d\n", f[1]);
    return 0;
}