제출 #623366

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
623366		MilosMilutinovic	Designated Cities (JOI19_designated_cities)	C++14	100 / 100	547 ms	57776 KiB

designated_cities

/**
 *    author:  wxhtzdy
 *    created: 05.08.2022 10:18:20
**/
#include <bits/stdc++.h>

using namespace std;

class segtree {
  public:
  struct node {
    // don't forget to set default value (used for leaves)
    // not necessarily neutral element!
    long long mx = 0;
    long long add = 0;
    int id = 0;
    void apply(int l, int r, long long v) {
      mx += v;
      add += v;
    }
  };
  node unite(const node &a, const node &b) const {
    node res;
    res.mx = max(a.mx, b.mx);
    res.id = (a.mx == res.mx ? a.id : b.id);
    return res;
  }
  inline void push(int x, int l, int r) {
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    if (tree[x].add != 0) {
      tree[x + 1].apply(l, y, tree[x].add);
      tree[z].apply(y + 1, r, tree[x].add);
      tree[x].add = 0;
    }
  }
  inline void pull(int x, int z) {
    tree[x] = unite(tree[x + 1], tree[z]);
  }
  int n;
  vector<node> tree;
  void build(int x, int l, int r) {
    tree[x].id = l;
    if (l == r) {
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y);
    build(z, y + 1, r);
    pull(x, z);
  }
  template <typename M>
  void build(int x, int l, int r, const vector<M> &v) {
    if (l == r) {
      tree[x].apply(l, r, v[l]);
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y, v);
    build(z, y + 1, r, v);
    pull(x, z);
  }
  node get(int x, int l, int r, int ll, int rr) {
    if (ll <= l && r <= rr) {
      return tree[x];
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    node res{};
    if (rr <= y) {
      res = get(x + 1, l, y, ll, rr);
    } else {
      if (ll > y) {
        res = get(z, y + 1, r, ll, rr);
      } else {
        res = unite(get(x + 1, l, y, ll, rr), get(z, y + 1, r, ll, rr));
      }
    }
    pull(x, z);
    return res;
  }
  template <typename... M>
  void modify(int x, int l, int r, int ll, int rr, const M&... v) {
    if (ll <= l && r <= rr) {
      tree[x].apply(l, r, v...);
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    if (ll <= y) {
      modify(x + 1, l, y, ll, rr, v...);
    }
    if (rr > y) {
      modify(z, y + 1, r, ll, rr, v...);
    }
    pull(x, z);
  }
  int find_first_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
    if (l == r) {
      return l;
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[x + 1])) {
      res = find_first_knowingly(x + 1, l, y, f);
    } else {
      res = find_first_knowingly(z, y + 1, r, f);
    }
    pull(x, z);
    return res;
  }
  int find_first(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
    if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_first_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (ll <= y) {
      res = find_first(x + 1, l, y, ll, rr, f);
    }
    if (rr > y && res == -1) {
      res = find_first(z, y + 1, r, ll, rr, f);
    }
    pull(x, z);
    return res;
  }
  int find_last_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
    if (l == r) {
      return l;
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[z])) {
      res = find_last_knowingly(z, y + 1, r, f);
    } else {
      res = find_last_knowingly(x + 1, l, y, f);
    }
    pull(x, z);
    return res;
  }
  int find_last(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
    if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_last_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (rr > y) {
      res = find_last(z, y + 1, r, ll, rr, f);
    }
    if (ll <= y && res == -1) {
      res = find_last(x + 1, l, y, ll, rr, f);
    }
    pull(x, z);
    return res;
  }
  segtree(int _n) : n(_n) {
    assert(n > 0);
    tree.resize(2 * n - 1);
    build(0, 0, n - 1);
  }
  template <typename M>
  segtree(const vector<M> &v) {
    n = v.size();
    assert(n > 0);
    tree.resize(2 * n - 1);
    build(0, 0, n - 1, v);
  }
  node get(int ll, int rr) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return get(0, 0, n - 1, ll, rr);
  }
  node get(int p) {
    assert(0 <= p && p <= n - 1);
    return get(0, 0, n - 1, p, p);
  }
  template <typename... M>
  void modify(int ll, int rr, const M&... v) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    modify(0, 0, n - 1, ll, rr, v...);
  }
  // find_first and find_last call all FALSE elements
  // to the left (right) of the sought position exactly once
  int find_first(int ll, int rr, const function<bool(const node&)> &f) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_first(0, 0, n - 1, ll, rr, f);
  }
  int find_last(int ll, int rr, const function<bool(const node&)> &f) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_last(0, 0, n - 1, ll, rr, f);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n;
  cin >> n;
  vector<vector<array<int, 3>>> g(n);
  long long total = 0;
  for (int i = 0; i < n - 1; i++) {
    int x, y, w0, w1;
    cin >> x >> y >> w0 >> w1;
    --x; --y;
    g[x].push_back({y, w1, w0});
    g[y].push_back({x, w0, w1});
    total += w0;
    total += w1;
  }                       
  vector<long long> dp(n);
  vector<int> que(1, 0); 
  vector<bool> vis(n);
  vis[0] = true; 
  for (int b = 0; b < (int) que.size(); b++) {
    int i = que[b];
    for (auto& p : g[i]) {
      int j = p[0];
      if (!vis[j]) {
        dp[0] += p[1];
        que.push_back(j);
        vis[j] = true;
      }
    }
  }       
  vector<long long> down(n);
  function<void(int, int)> Dp = [&](int v, int pr) {
    for (auto& p : g[v]) {
      int u = p[0];
      if (u != pr) {
        dp[u] = dp[v] - p[1] + p[2];
        Dp(u, v);
        down[v] = max(down[v], down[u] + p[2]);
      }
    }
  };
  Dp(0, 0);
  int root = max_element(dp.begin(), dp.end()) - dp.begin();
  vector<long long> ans(n + 1);
  ans[1] = dp[root];
  long long best = -1e18;
  int who = -1;
  function<void(int, int, long long)> Dfs = [&](int v, int pr, long long up) {
    long long me = max(up, down[v]) + dp[v];
    if (me > best) {
      best = me;
      who = v;
    }    
    long long f0 = -1e18;
    long long f1 = -1e18;
    int id = -1;
    for (auto& p : g[v]) {
      long long he = down[p[0]] + p[2];
      if (he > f0) {
        f0 = he;
        id = p[0];
      } else {
        f1 = max(f1, he);
      }
    }
    for (auto& p : g[v]) {
      int u = p[0];
      if (u == pr) {
        continue;
      }
      long long new_up = max(0LL, up);
      if (u != id) {
        new_up = max(new_up, f0);
      } else {
        new_up = max(new_up, f1);
      }
      Dfs(u, v, new_up + p[1]);
    }
  };
  Dfs(0, 0, -1e18);
  root = who;
  vector<int> up(n);
  vector<int> par(n);
  vector<int> tin(n);
  vector<int> tout(n);
  vector<int> ver(n);
  int T = -1;      
  segtree st(n);
  function<void(int, int)> Go = [&](int v, int pr) {
    tin[v] = ++T;
    ver[T] = v;
    par[v] = pr;
    for (auto& p : g[v]) {
      int u = p[0];
      if (u != pr) {
        Go(u, v);
        up[u] = p[2];
        st.modify(tin[u], tout[u], p[2]);
      }
    }
    tout[v] = T;
  };
  Go(root, root);
  vector<bool> was(n);
  was[root] = true;            
  long long f = dp[root];
  auto Rem = [&](int x) {
    while (!was[x]) {
      st.modify(tin[x], tout[x], -up[x]);
      f += up[x];
      was[x] = true;      
      x = par[x];
    }
  };
  for (int i = 2; i <= n; i++) {     
    Rem(ver[st.get(0, n - 1).id]);        
    ans[i] = f;
  }  
  int q;
  cin >> q;
  while (q--) {
    int x;
    cin >> x;
    cout << total - ans[x] << '\n'; 
  }                                     
  return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 17 / 17
• Subtask 5: 17 / 17
• Subtask 6: 44 / 44