做了一天多。。。我可以滚了。。。

开始以为没有边权,写了树剖,后来发现带边权。。。emmmm

在限制时间内尽量让所有的军队网上爬,有能力爬到根节点的存起来

存起来的点里面,有些可能不能往外爬(需要待在原本的子树内),所以要让一个最小的留在里面

struct Edge {
  int v, w, next;
}G[MAXN]; int head[MAXN>>1], n, m, anc[MAXN>>1][16], Pos[MAXN>>1], id[MAXN>>1];
ll dis[MAXN>>1][16], ans = -1, l, r, Min[MAXN>>1], r2;
bool cnt[MAXN>>1], vis[MAXN>>1];

inline void add(int u, int v, int w) {
  static int tot = 0;
  G[++tot] = (Edge) {v, w, head[u]}; head[u] = tot;
}

inline int Log2(int x) {
  return 31 - __builtin_clz(x);
}
pair<ll,int> a[MAXN>>1], b[MAXN>>1];
inline bool cmp(const pair<ll,int> &a, const pair<ll, int>&b) {
  return a.xx > b.xx;
}
inline bool dfs3(int u, int fa) {
  if (cnt[u]) return 1;
  bool flag = u == 1;
  for(int i = head[u]; i; i = G[i].next) {
    if (G[i].v == fa) continue;
    if (!dfs3(G[i].v, u)) {
      flag = 0;
      if (u == 1) b[++r2] = mp(G[i].w, G[i].v);
      else return 0;
    }
    else if (u != 1) flag = 1;
  }
  return flag;
}

inline bool check(ll X) {
  fill(cnt+1, cnt+1+m, 0);
  fill(vis+1, vis+1+m, 0);
  int l1 = 1, r1 = 0; r2 = 0;
  for(int i = head[1]; i; i = G[i].next) id[G[i].v] = 0, Min[G[i].v] = infl;
  lop(i,1,m) {
    int u = Pos[i]; ll tot = 0;
    dlop(j,Log2(n),0) 
      if (anc[u][j] > 1 && tot + dis[u][j] <= X) tot += dis[u][j], u = anc[u][j];
    if (anc[u][0] == 1 && tot + dis[u][0] <= X) {
      a[++r1] = mp(X - tot - dis[u][0], i); 
      if (a[r1].xx < Min[u]) Min[u] = a[r1].xx, id[u] = i;
    }
    else cnt[u] = 1;
  }
  if (dfs3(1, 0)) return 1;  sort(a+1, a+1+r1, cmp), sort(b+1, b+1+r2, cmp);
  if (r1 < r2) return 0;
  lop(l2,1,r2) {
    if (id[b[l2].yy] && !vis[id[b[l2].yy]]) {vis[id[b[l2].yy]] = 1; continue;}
    while(l1 <= r1 && (vis[a[l1].yy] || a[l1].xx < b[l2].xx)) ++l1;
    if (l1 > r1) return 0; vis[a[l1].yy] = 1;
  }
  return 1;
}
inline void dfs(int u, int fa, ll cur) {
  chmax(r, cur);
  for(int i = head[u]; i; i = G[i].next) {
    int v = G[i].v, w = G[i].w;
    if (v == fa) continue;
    anc[v][0] = u, dis[v][0] = w;
    dfs(v, u, cur + w);
  }
}

int main() {
  in, n;
  lop(i,1,n-1) {
    int u, v, w; in, u, v, w; add(u, v, w), add(v, u, w);
  }
  dfs(1, 0, 0);
  int Max = 0, cnt = 0;
  for(int i = head[1]; i; i = G[i].next) chmax(Max, G[i].w), ++cnt;
  in, m;
  if (m < cnt) return puts("-1"), 0; 
  r += Max;
  lop(i,1,n)
    lop(j,1,Log2(n)) anc[i][j] = anc[anc[i][j-1]][j-1];
  lop(i,1,n) 
    lop(j,1,Log2(n)) dis[i][j] = dis[i][j-1] + dis[anc[i][j-1]][j-1];
  lop(i,1,m) in, Pos[i];
  while(l <= r) {
    if (check(mid)) ans = mid, r = mid-1;
    else l = mid+1;
  }
  out, ans;
  return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注