Submission #1191854

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191854		lopkus	Election Campaign (JOI15_election_campaign)	C++20	20 / 100	1098 ms	57232 KiB

election_campaign

#include <bits/stdc++.h>

#define int int64_t

const int N = 1e5 + 5;

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;
  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);
  }
  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) {
      for(auto a : g[u]) {
        if(a == lca.P[u]) {
          continue;
        }
        sum += dp[a];
      }
      sum -= dp[u];
      u = lca.P[u];
    }
    while(v != ath) {
      for(auto a : g[v]) {
        if(a == lca.P[v]) {
          continue;
        }
        sum += dp[a];
      }
      sum -= dp[v];
      v = lca.P[v];
    }
    for(auto a : g[ath]) {
      if(a == lca.P[ath]) {
        continue;
      }
      sum += dp[a];
    }
    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 ath : g[v]) {
      if(ath == p) {
        continue;
      }
      dp[v] += dp[ath];
    }
    for(auto [l, r, d] : ty[v]) {
      dp[v] = std::max(dp[v], Df(l, r) + d);
    }
  };
  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: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 30
• Subtask 5: 10 / 10
• Subtask 6: 0 / 40