- 疫情控制
- 2017-10-25 16:38:12 @
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<algorithm>
#define MAXN 50002
#define MAXM MAXN
using namespace std;
typedef long long ll;
template<typename T>
inline void getint(T &num){
char ch;
while(!isdigit(ch = getchar()));
num = ch - '0';
while(isdigit(ch = getchar())) num = (num << 1) + (num << 3) + ch - '0';
}
int n, m;
int army[MAXM];
struct tEdge{
int np; ll w;
tEdge *nxt;
};
struct tGraph{
#define MAXV MAXN
#define MAXE (MAXN * 2)
tEdge E[MAXE], *V[MAXV];
int tope;
tGraph(): tope(0) {}
inline void addedge(int u, int v, ll w){
E[++tope].np = v, E[tope].w = w;
E[tope].nxt = V[u], V[u] = &E[tope];
}
} G;
int fa[MAXN];
ll fadis[MAXN];
bool isborder[MAXN];
inline void Init_fa(int u){
isborder[u] = 1;
for(register tEdge *ne = G.V[u]; ne; ne = ne->nxt){
if(ne->np == fa[u]) continue;
fa[ne->np] = u, fadis[ne->np] = ne->w, isborder[u] = 0;
Init_fa(ne->np);
}
}
int jmp[16][MAXN];
ll jmpdis[16][MAXN];
inline void Init_redbl(){
for(register int i = 1; i <= n; i++) jmp[0][i] = fa[i], jmpdis[0][i] = fadis[i];
for(register int dbl = 1; dbl < 16; dbl++)
for(register int i = 1; i <= n; i++){
jmp[dbl][i] = jmp[dbl - 1][jmp[dbl - 1][i]];
jmpdis[dbl][i] = jmpdis[dbl - 1][i] + jmpdis[dbl - 1][jmp[dbl - 1][i]];
}
}
int dep[MAXM], insub[MAXM];
inline void Init_army(){
for(register int i = 1; i <= m; i++){
int cur = army[i];
for(register int dbl = 15; dbl >= 0; dbl--)
if(jmp[dbl][cur] > 1) dep[i] += jmpdis[dbl][cur], cur = jmp[dbl][cur];
insub[i] = cur, dep[i] += fadis[cur];
}
}
struct tSupply{
int rem, id;
inline bool operator < (const tSupply sup2) const {return rem > sup2.rem;}
} supply[MAXM];
struct tDemand{
int req, sub;
inline bool operator < (const tDemand dem2) const {return req > dem2.req;}
} demand[MAXM];
int tops, topd;
int mins[MAXM]; // 根的每个子树各自的军队中能走到根且剩余距离最小的编号
bool isundercon[MAXN], used[MAXN];
inline bool dfs(int u){
if(isundercon[u]) return 0;
if(isborder[u]) return 1;
for(register tEdge *ne = G.V[u]; ne; ne = ne->nxt)
if(ne->np != fa[u] && dfs(ne->np)) return 1;
return 0;
}
inline bool check(int tim){
supply[0].rem = 0x3f3f3f3f;
memset(isundercon, 0, sizeof(isundercon)), tops = 0, topd = 0;
memset(mins, 0, sizeof(mins)), memset(used, 0, sizeof(used));
for(register int i = 1; i <= m; i++){
if(tim >= dep[i]){
supply[++tops].rem = tim - dep[i], supply[tops].id = tops;
if(supply[tops].rem < supply[mins[insub[i]]].rem) mins[insub[i]] = tops;
}
else{
int cur = army[i], rem = tim;
for(register int dbl = 15; dbl >= 0; dbl--)
if(jmp[dbl][cur] && rem >= jmpdis[dbl][cur])
rem -= jmpdis[dbl][cur], cur = jmp[dbl][cur];
isundercon[cur] = 1;
}
}
for(register tEdge *ne = G.V[1]; ne; ne = ne->nxt)
if(dfs(ne->np)) demand[++topd].req = ne->w, demand[topd].sub = ne->np;
sort(supply + 1, supply + tops + 1), sort(demand + 1, demand + topd + 1);
for(register int i = 1, j = 1; j <= topd; j++){
if(mins[demand[j].sub] && !used[mins[demand[j].sub]]) {used[mins[demand[j].sub]] = 1; continue;}
while(i <= tops && used[supply[i].id]) i++;
if(i > tops || demand[j].req > supply[i].rem) return 0;
used[supply[i++].id] = 1;
}
return 1;
}
int main(){
getint(n);
for(register int i = 1; i < n; i++){
int u, v; ll w;
getint(u), getint(v), getint(w);
G.addedge(u, v, w), G.addedge(v, u, w);
}
Init_fa(1), Init_redbl();
getint(m);
for(register int i = 1; i <= m; i++) getint(army[i]);
Init_army();
int lft = 0, rt = 500000;
while(lft < rt){
int mid = lft + rt >> 1;
if(check(mid)) rt = mid;
else lft = mid + 1;
}
if(lft < 500000) printf("%d\n", lft);
else printf("-1\n");
}
0 条评论
目前还没有评论...