Submission #118905

#	Time	Username	Problem	Language	Result	Execution time	Memory
118905		IOrtroiii	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	478 ms	30632 KiB

election_campaign

#include <bits/stdc++.h>

using namespace std;

const int N = 100100;

struct Path {
   int from, to, cost;
   Path(int from, int to, int cost) : from(from), to(to), cost(cost){}
};

int n;
vector<int> g[N];
int dep[N], par[17][N];
int tin[N], tout[N], tt;
int f[N], sf[N];
vector<Path> ps[N];

void dfs(int u, int p) {
   tin[u] = ++tt;
   for (int i = 1; i < 17; ++i) {
      par[i][u] = par[i - 1][par[i - 1][u]];
   }
   for (int v : g[u]) if (v != p) {
      dep[v] = dep[u] + 1;
      par[0][v] = u;
      dfs(v, u);
   }
   tout[u] = tt;
}

int lca(int u, int v) {
   if (dep[u] > dep[v]) swap(u, v);
   for (int i = 16; i >= 0; --i) {
      if (dep[par[i][v]] >= dep[u]) {
         v = par[i][v];
      }
   }
   if (u == v) return u;
   for (int i = 16; i >= 0; --i) {
      if (par[i][u] != par[i][v]) {
         u = par[i][u];
         v = par[i][v];
      }
   }
   return par[0][u];
}

int t[N << 2];

void add(int v, int l, int r, int L, int R, int val) {
   if (L <= l && r <= R) {
      t[v] += val;
      return;
   }
   int md = (l + r) >> 1;
   if (L <= md) add(v << 1, l, md, L, R, val);
   if (md < R) add(v << 1 | 1, md + 1, r, L, R, val);
}

int get(int v, int l, int r, int p) {
   if (l == r) {
      return t[v];
   }
   int md = (l + r) >> 1;
   int ans = t[v];
   if (p <= md) ans += get(v << 1, l, md, p);
   else ans += get(v << 1 | 1, md + 1, r, p);
   return ans;
}

void solve(int u) {
   for (int v : g[u]) if (v != par[0][u]) {
      solve(v);
      sf[u] += f[v];
   }
   for (int v : g[u]) if (v != par[0][u]) {
      add(1, 1, n, tin[v], tout[v], sf[u] - f[v]);
   }
   f[u] = sf[u];
   for (auto p : ps[u]) {
      int from = p.from, to = p.to, cost = p.cost;
      int val = sf[from] + sf[to] - sf[u] + cost;
      val += get(1, 1, n, tin[from]);
      val += get(1, 1, n, tin[to]);
      f[u] = max(f[u], val);
   }
}

int main() {
   ios_base::sync_with_stdio(false);
   cin >> n;
   for (int i = 1; i < n; ++i) {
      int u, v;
      cin >> u >> v;
      g[u].emplace_back(v);
      g[v].emplace_back(u);
   }
   par[0][1] = 1;
   dfs(1, 1);
   int m;
   cin >> m;
   for (int i = 1; i <= m; ++i) {
      int u, v, w;
      cin >> u >> v >> w;
      int a = lca(u, v);
      ps[a].emplace_back(u, v, w);
   }
   solve(1);
   cout << f[1] << '\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