Submission #1148472

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148472		fryingduc	Election Campaign (JOI15_election_campaign)	C++20	100 / 100	135 ms	32908 KiB

election_campaign

#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "D:\\debug.h"
#else
#define debug(...)
#endif

const int maxn = 1e5 + 5;
const int LG = 18;
int n, m;
vector<int> g[maxn];
int a[maxn], b[maxn], c[maxn], d[maxn];
vector<int> que[maxn];
int sz[maxn], par[maxn], h[maxn], up[maxn][LG + 1];
int tin[maxn], tout[maxn], timer, rev[maxn];
int head[maxn];
long long f[maxn], fsum[maxn];

void pre_dfs(int u, int prev) {
  sz[u] = 1;
  for (auto v:g[u]) {
    if (v == prev) continue;
    h[v] = h[u] + 1;
    up[v][0] = par[v] = u;
    for (int i = 1; i <= LG; ++i) {
      up[v][i] = up[up[v][i - 1]][i - 1];
    }
    pre_dfs(v, u);
    sz[u] += sz[v];
  }  
}

void hld(int u, int prev) {
  if (!head[u]) {
    head[u] = u;
  }
  tin[u] = ++timer;
  rev[timer] = u;
  int big_child = -1;
  for (auto v:g[u]) {
    if (v == prev) continue;
    if (big_child == -1 || sz[big_child] < sz[v]) {
      big_child = v;
    }
  }
  if (big_child != -1) {
    head[big_child] = head[u];
    hld(big_child, u);
  }
  for (auto v:g[u]) {
    if (v == prev || v == big_child) continue;
    hld(v, u);
  }
  tout[u] = timer;
}

int lca(int u, int v) {
  if (h[u] < h[v]) swap(u, v);
  for (int i = LG; i >= 0; --i) {
    if ((h[u] - h[v]) >> i & 1) {
      u = up[u][i];
    }
  }
  if (u == v) return u;
  for (int i = LG; i >= 0; --i) {
    if (up[u][i] != up[v][i]) {
      u = up[u][i], v = up[v][i];
    }
  }
  return up[u][0];
}

long long bit[maxn];
void update(int i, long long val) {
  for (; i <= n; i += i & (-i)) {
    bit[i] += val;
  }
}

long long get(int i) {
  long long ans = 0;
  for (; i > 0; i -= i & (-i)) {
    ans += bit[i];
  }
  return ans;
}

long long get(int l, int r) {
  return l > r ? 0 : get(r) - get(l - 1);
}

long long get_path(int u, int v) {
  long long res = 0;
  while (head[u] != head[v]) {
    if (h[head[u]] > h[head[v]]) swap(u, v);
    res += get(tin[head[v]], tin[v]);
    v = par[head[v]];
  }
  if (h[u] > h[v]) swap(u, v);
  res += get(tin[u], tin[v]);
  return res;
}

void dfs(int u, int prev) {
  for (auto v:g[u]) {
    if (v == prev) continue;
    dfs(v, u);
    f[u] = max(f[u], f[v]);
    fsum[u] += f[v];
  }
  f[u] = max(f[u], fsum[u]);
  update(tin[u], fsum[u]);
  for (auto i:que[u]) {
    f[u] = max(f[u], get_path(a[i], b[i]) + c[i]);
  }
  update(tin[u], -f[u]);
}

void solve() {
  cin >> n;
  for (int i = 1; i < n; ++i) {
    int u, v; cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  pre_dfs(1, 0);
  par[1] = 1;
  hld(1, 0);
  cin >> m;
  for (int i = 1; i <= m; ++i) {
    cin >> a[i] >> b[i] >> c[i];
    d[i] = lca(a[i], b[i]);
    que[lca(a[i], b[i])].push_back(i);
  }
  dfs(1, 0);
  long long res = 0;
  for (int i = 1; i <= n; ++i) {
    res = max(res, max(f[i], fsum[i]));
  }
  cout << res;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  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