Submission #42672

#	Time	Username	Problem	Language	Result	Execution time	Memory
42672		funcsr	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	378 ms	179772 KiB

election_campaign

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cassert>
#include <functional>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define MAX_N (1<<17)
#define pb push_back
#define _1 first
#define _2 second
struct HLDecomposition {
  int N;
  vector<vector<int> > G;
  vector<int> head, par, next, tid;
  HLDecomposition(int N) : N(N), G(N), head(N, -1), par(N, -1), next(N, -1), tid(N, -1) {}

  void add_edge(int x, int y) {
    G[x].pb(y), G[y].pb(x);
  }
  int dfs(int x, int p) {
    par[x] = p;
    int s = 1, mc = 0;
    for (int t : G[x]) if (t != p) {
      int w = dfs(t, x);
      if (w > mc) mc = w, next[x] = t;
      s += w;
    }
    return s;
  }
  void build() {
    assert(dfs(0, -1) == N);
    queue<int> q;
    int k = 0;
    q.push(0);
    while (!q.empty()) {
      int h = q.front(); q.pop();
      for (int v=h; v!=-1; v=next[v]) tid[v] = k++, head[v] = h;
      for (int v=h; v!=-1; v=next[v]) for (int t : G[v]) if (tid[t] == -1) q.push(t);
    }
    assert(k == N);
  }
  int lca(int u, int v) {
    if (tid[u] < tid[v]) swap(u, v);
    if (head[u] == head[v]) return v;
    return lca(par[head[u]], v);
  }
  void for_each(int u, int v, function<void(int, int)> f) {
    if (tid[u] < tid[v]) swap(u, v);
    if (head[u] == head[v]) return f(tid[v], tid[u]);
    f(tid[head[u]], tid[u]);
    return for_each(par[head[u]], v, f);
  }
};

struct BIT {
  int n;
  vector<int> xs;
  BIT(int n) : n(n), xs(n+1, 0) {}
  void add(int i, int v) {
    for (int x=i+1; x<=n; x+=x&-x) xs[x] += v;
  }
  int sum(int i) {
    int s = 0;
    for (int x=i+1; x>0; x-=x&-x) s += xs[x];
    return s;
  }
  int sum(int l, int r) {
    if (l > r) return 0;
    return sum(r) - sum(l-1);
  }
};

int N, M;
int A[100000], B[100000], C[100000];
HLDecomposition hld(0);
BIT bit(0);

vector<int> G[100000];
vector<int> Q[100000];
int dp[100000];

void dfs(int x, int p) {
  int sum = 0;
  for (int t : G[x]) if (t != p) {
    dfs(t, x);
    sum += dp[t];
  }
  dp[x] = sum;
  for (int id : Q[x]) {
    int u = A[id], v = B[id], w = C[id]+sum;
    hld.for_each(u, v, [&](int l, int r) { w += bit.sum(l, r); });
    dp[x] = max(dp[x], w);
  }
  bit.add(hld.tid[x], sum-dp[x]);
}

int main() {
  cin >> N;
  hld = HLDecomposition(N);
  bit = BIT(N);
  rep(i, N-1) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    G[u].pb(v);
    G[v].pb(u);
    hld.add_edge(u, v);
  }
  hld.build();

  cin >> M;
  rep(i, M) {
    cin >> A[i] >> B[i] >> C[i];
    A[i]--, B[i]--;
    Q[hld.lca(A[i], B[i])].pb(i);
  }
  dfs(0, -1);
  cout << dp[0] << "\n";
  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