题解 | 算法竞赛进阶指南 疫情控制

思路

显而易见,答案具有单调性,时间越长,越容易控制疫情.所以很容易想到二分时间.
首先,占据一个点肯定不如占据这个点的父亲,因此时间内到达不了号节点的尽力往上跳就可以了(暴力跳可不行,需要使用倍增).
还有一些军队可能会经过号节点到达其他号节点的儿子节点.
先来证明一个结论:若些军队的集合不经过号节点能到达号节点的儿子节点,并且其不能到达号节点又回到,还有其他不经过号节点的军队还未占据,中的某一支军队(当然是还能走的路程最小的那支)来占据号节点不会更劣.
这个其实不难证明,若来自的另一个儿子节点的军队来占据,而的军队都穿过去占据其他节点,说明在节点时还能走的路程大于等于,而中的军队还能走的路程都小于,得到的解不可能更优.
接下来还要处理那些经过的军队与还需要占据的的子节点如何配对.
直接使用贪心,军队还能走的路程从大到小排序,子节点按照与距离从大到小排序,按此配对即可.如果不能完成配对,说明时间不够.这样复杂度为,一个是二分的,还有一个是往上跳时倍增的.

代码

#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i )
#define fd( i, b, e ) for ( int i(b), I(e); i >= I; --i )
#define go( i, b ) for ( int i(b), v(to[i]); i; v = to[i = nxt[i]] )
template<typename T> inline void cmax( T &x, T y ){ x < y ? x = y : x; }
template<typename T> inline void cmin( T &x, T y ){ y < x ? x = y : x; }
#define getchar() ( p1 == p2 && ( p1 = bf, p2 = bf + fread( bf, 1, 1 << 21, stdin ), p1 == p2 ) ? EOF : *p1++ )
char bf[1 << 21], *p1(bf), *p2(bf);
template<typename T>
inline void read( T &x ){ char t(getchar()), flg(0); x = 0;
    for ( ; !isdigit(t); t = getchar() ) flg = t == '-';
    for ( ; isdigit(t); t = getchar() ) x = x * 10 + ( t & 15 );
    flg ? x = -x : x;
}

clock_t t_bg, t_ed;
const int MAXN = 50005;
int N, M;
int hd[MAXN], nxt[MAXN<<1], to[MAXN<<1], val[MAXN<<1], tot;
inline void addedge( int x, int y, int z ){
    nxt[++tot] = hd[x], hd[x] = tot, to[tot] = y, val[tot] = z,
    nxt[++tot] = hd[y], hd[y] = tot, to[tot] = x, val[tot] = z;
}
int fa[MAXN][20], dep[MAXN], w[MAXN], n, m; i64 s[MAXN], h[MAXN], g[MAXN];
bool b[MAXN];
vector<i64> v[MAXN];

void DFS( int u ){
    dep[u] = dep[fa[u][0]] + 1;
    fp( i, 1, 15 ) fa[u][i] = fa[fa[u][i - 1]][i - 1];
    go( i, hd[u] ) if ( v != fa[u][0] ) fa[v][0] = u, s[v] = s[u] + val[i], DFS(v);
}
void dfs( int u ){
    if ( !b[u] ){
        if ( nxt[hd[u]] ) b[u] = 1;
        go( i, hd[u] ) if ( v != fa[u][0] ) dfs(v), b[u] &= b[v];
    }
    if ( dep[u] == 2 && v[u].size() ){
        if ( b[u] ) fp( i, 0, v[u].size() - 1 ) h[++n] = v[u][i] - s[u];
        else{ b[u] = 1, sort( v[u].begin(), v[u].end() ); fp( i, 1, (int)v[u].size() - 1 ) h[++n] = v[u][i] - s[u]; }
    }
} bool cmp( int x, int y ){ return x > y; }

bool check( i64 S ){
    n = m = 0;
    memset( b, 0, sizeof b );
    fp( i, 1, N ) v[i].clear();
    fp( i, 1, M ){
        int x(w[i]), t(x); i64 y(S);
        fd( j, 15, 0 ) if ( fa[t][j] > 1 && s[x] - s[fa[t][j]] <= y ) t = fa[t][j];
        y -= s[x] - s[t];
        if ( dep[t] == 2 && y >= (s[t] << 1) ) h[++n] = y - s[t];
        else if ( dep[t] == 2 && y >= s[t] ) v[t].push_back(y);
        else b[t] = 1;
    } dfs(1);
    go( i, hd[1] ) if ( !b[v] ) g[++m] = s[v];
    if ( n < m ) return 0;
    sort( h + 1, h + n + 1, cmp ), sort( g + 1, g + m + 1, cmp );
    fp( i, 1, m ) if ( h[i] < g[i] ) return 0;
    return 1;
}

signed main(){
    t_bg = clock();
    read(N); int x, y, z; i64 l(1), r(0), mid, ans(-1);
    fp( i, 2, N ) read(x), read(y), read(z), addedge( x, y, z ), r += z;
    DFS(1), read(M); fp( i, 1, M ) read(w[i]);
    while( l <= r ){
        mid = ( l + r ) >> 1;
        if ( check(mid) ) r = mid - 1, ans = mid;
        else l = mid + 1;
    } printf( "%lld\n", ans );
    t_ed = clock();
    fprintf( stderr, "\n========info========\ntime : %.3f\n====================\n", (double)( t_ed - t_bg ) / CLOCKS_PER_SEC );
    return 0;
}