Submission #1191973

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191973		lopkus	Election Campaign (JOI15_election_campaign)	C++20	100 / 100	221 ms	59124 KiB

election_campaign

#include <bits/stdc++.h>

#define int64_t int

const int N = 2e5 + 5;

struct segtree{
    int t[4 * N] = {0};
    int64_t query(int v, int tl, int tr, int l, int r) {
        if(tl > r || tr < l) {
            return 0;
        }
        if(tl >= l && tr <= r) {
            return t[v];
        }
        int tm = (tl + tr) / 2;
        return (query(v * 2, tl, tm, l, r) + query(v * 2 + 1, tm + 1, tr, l, r));
    }
    void update(int v, int tl, int tr, int index, int64_t value) {
        if(tl == tr) {
            t[v] = value;
        }
        else {
            int tm = (tl + tr) / 2;
            if(index <= tm) {
                update(v * 2, tl, tm, index, value);
            }
            else {
                update(v * 2 + 1, tm + 1, tr, index, value);
            }
            t[v] = (t[v * 2] + t[v * 2 + 1]);
        }
    }
}seg;

struct HLD {
  std::vector<std::vector<int>> adj;
  std::vector<int> sub_tree, in, color, parent, dep;
  void create(int n) {
    sub_tree.resize(n + 1, 1);
    adj.resize(n + 1);
    in.resize(n + 1);
    color.resize(n + 1);
    parent.resize(n + 1);
    dep.resize(n + 1, 1);
  }
  void add(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  void dfs(int v, int p) {
    for(auto u : adj[v]) {
      if(u == p) {
        continue;
      }
      dep[u] = dep[v] + 1;
      dfs(u, v);
      sub_tree[v] += sub_tree[u];
    }
  }
  int t = 1;
  void build(int v, int p, int c) {
    parent[v] = p;
    in[v] = t++;
    int biggestsz = - 1;
    int thebiggest = - 1;
    color[v] = c;
    for(auto u : adj[v]) {
      if(u == p) {
        continue;
      }
      if(biggestsz < sub_tree[u]) {
        thebiggest = u;
        biggestsz = sub_tree[u];
      }
    }
    if(thebiggest == - 1) {
      return;
    }
    build(thebiggest, v, c);
    for(auto u : adj[v]) {
      if(u == p || u == thebiggest) {
        continue;
      }
      build(u, v, u);
    }
  }
  int64_t query(int u, int v) {
    int64_t ans = 0;
    while(color[u] != color[v]) {
      if(dep[color[u]] < dep[color[v]]) {
        std::swap(u, v);
      }
      ans += seg.query(1, 1, N - 1, in[color[u]], in[u]);
      u = parent[color[u]];
    }
    if(dep[u] > dep[v]) {
      std::swap(u, v);
    }
    ans += seg.query(1, 1, N - 1, in[u], in[v]);
    return ans;
  }
  void update(int u, int64_t val) {
    seg.update(1, 1, N - 1, in[u], val);
  }
}hld;

struct Lca{
    std::vector<int>adj[N];
    int in[N];
    int out[N];
    int timer=1;
    int P[N];
    int Log(int n){
        int logs[n+1];
        logs[1]=0;
        for(int i=2;i<=n;i++)logs[i]=logs[i/2]+1;
        return logs[n];
    }
    int up[N][30];
    void build(int n){
        up[1][0]=1;
        for(int i=2;i<=n;i++)up[i][0]=P[i];
        for(int i=1;i<=29;i++){
            for(int j=1;j<=n;j++){
                up[j][i]=up[up[j][i-1]][i-1];
            }
        }
    }
    void connect(int u,int v){
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    void dfs(int x,int father){
        in[x]=timer++;
        P[x]=father;
        for(auto it:adj[x]){
            if(it!=father)dfs(it,x);
        }
        out[x]=timer;
    }
    int in_tree(int u,int v){
        return in[u]<=in[v]&&out[u]>=out[v];
    }
    int lca(int u,int v){
        if(u==v)return u;
        if(in_tree(u,v))return u;
        if(in_tree(v,u))return v;
        for(int i=29;i>=0;i--){
            if(!in_tree(up[u][i],v)){
                u=up[u][i];
            }
        }
        return up[u][0];
    }
}lca;

void solve() {
  int n;
  std::cin >> n;
  hld.create(n);
  std::vector<std::vector<int>> g(n + 1);
  for(int i = 1; i < n; i++) {
    int u, v;
    std::cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
    lca.connect(u, v);
    hld.add(u, v);
  }
  hld.dfs(1, 0);
  hld.build(1, 0, 1);
  lca.dfs(1, 0);
  lca.build(n);
  std::vector<int> dp(n + 1, 0);
  std::vector<std::array<int, 3>> ty[n + 1];
  int q;
  std::cin >> q;
  while(q--) {
    int u, v, w;
    std::cin >> u >> v >> w;
    ty[lca.lca(u, v)].push_back({u, v, w});
  }
  std::vector<int> s(n + 1);
  /**
  std::function<int(int, int)> Df = [&] (int u, int v) {
    int ath = lca.lca(u, v);
    int sum = 0;
    while(u != ath) {
      sum += s[u] - dp[u];
      u = lca.P[u];
    }
    while(v != ath) {
      sum += s[v] - dp[v];
      v = lca.P[v];
    }
    sum += s[ath];
    return sum;
  };**/
  std::function<void(int, int)> dfs = [&] (int v, int p) {
    for(auto u : g[v]) {
      if(u == p) {
        continue;
      }
      dfs(u, v);
    }
    for(auto u : g[v]) {
      if(u == p) {
        continue;
      }
      s[v] += dp[u];
    }
    for(auto ath : g[v]) {
      if(ath == p) {
        continue;
      }
      dp[v] += dp[ath];
    }
    for(auto [l, r, d] : ty[v]) {
      dp[v] = std::max(dp[v], hld.query(l, r) + d + s[v]);
    }
    hld.update(v, s[v] - dp[v]);
  };
  dfs(1, 0);
  std::cout << dp[1];
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int t = 1;
  //std::cin >> t;
  while (t--) {
      solve();
  }

  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 30 / 30
• Subtask 5: 10 / 10
• Subtask 6: 40 / 40