Submission #961431

#	Time	Username	Problem	Language	Result	Execution time	Memory
961431		rxlfd314	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	177 ms	34772 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

constexpr int mxN = 100005;
int N, M;
vt<int> adj[mxN];

int szs[mxN], hson[mxN], parent[mxN], lift[mxN][17];
void dfs_szs(int i, int p) {
  FOR(j, 1, 16)
    lift[i][j] = lift[lift[i][j-1]][j-1];
  parent[i] = p;
  szs[i] = 1;
  hson[i] = -1;
  for (int j : adj[i])
    if (j != p) {
      lift[j][0] = i;
      dfs_szs(j, i);
      szs[i] += szs[j];
      if (hson[i] < 0 || szs[j] > szs[hson[i]])
        hson[i] = j;
    }
}

int head[mxN], tin[mxN], tout[mxN], timer;
void dfs_hld(int i) {
  tin[i] = timer++;
  if (hson[i] >= 0) {
    head[hson[i]] = head[i];
    dfs_hld(hson[i]);
  }
  for (int j : adj[i])
    if (j != parent[i] && j != hson[i]) {
      head[j] = j;
      dfs_hld(j);
    }
  tout[i] = timer-1;
}

bool ia(int a, int b) {
  return tin[a] <= tin[b] && tin[b] <= tout[a];
}

int LCA(int a, int b) {
  ROF(j, 16, 0)
    if (!ia(lift[a][j], b))
      a = lift[a][j];
  return ia(a, b) ? a : lift[a][0];
}

struct ST {
  int st[mxN<<1];
  void add(int i, int v) {
    for (st[i+=N] += v; i > 1; i >>= 1)
      st[i>>1] = st[i] + st[i^1];
  }
  void pset(int i, int v) {
    for (st[i+=N] = v; i > 1; i >>= 1)
      st[i>>1] = st[i] + st[i^1];
  }
  int query(int l, int r) {
    int ret = 0;
    for (l+=N, r+=N+1; l<r; l>>=1, r>>=1) {
      if (l & 1)
        ret += st[l++];
      if (r & 1)
        ret += st[--r];
    }
    return ret;
  }
} dp, sum_dp;

vt<ari3> paths[mxN];
void dfs(int i) {
  for (int j : adj[i])
    if (j != parent[i])
      dfs(j);
  
  int res = sum_dp.query(tin[i], tin[i]);
  for (auto [a, b, c] : paths[i]) {
    int x = sum_dp.query(tin[i], tin[i]) + c;
    FOR(_, 1, 2) {
      if (a != i) {
        for (; a >= 0 && tin[a] > tin[i]; a = parent[head[a]]) {
          int l = max(tin[head[a]], tin[i]+1);
          int r = tin[a];
          x += sum_dp.query(l, r);
          x -= dp.query(l, r);
        }
      }
      swap(a, b);
    }
    res = max(res, x);
  }
  #ifdef DEBUG
  cout << "dp[" << i+1 << "] = " << res << '\n';
  #endif
  
  dp.pset(tin[i], res);
  if (parent[i] >= 0)
    sum_dp.add(tin[parent[i]], res);
}

signed main() {
#ifndef DEBUG
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  cin >> N;
  FOR(_, 2, N) {
    int a, b;
    cin >> a >> b, a--, b--;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  dfs_szs(0, -1);
  dfs_hld(0);
  
  cin >> M;
  FOR(_, 1, M) {
    int a, b, c;
    cin >> a >> b >> c, a--, b--;
    paths[LCA(a, b)].push_back({a, b, c});
    #ifdef DEBUG
    cout << "LCA(" << a+1 << ", " << b+1 << ") = " << LCA(a, b)+1 << '\n';
    #endif
  }
  
  dfs(0);
  cout << dp.query(0, 0) << '\n';
}

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