Submission #1364103

#TimeUsernameProblemLanguageResultExecution timeMemory
1364103repmannElection Campaign (JOI15_election_campaign)C++20
100 / 100
137 ms28584 KiB
#include <bits/stdc++.h>
using namespace std;
int N, M;
int glob, L[100001], R[100001], DIST[100001], UP[20][100001];
int FT[100001];
int DP[2][100001];
vector <int> VG[100001];
vector <array <int, 3>> V[100001];
void Add(int i, int x)
{
  for(; i <= N; i += i & (-i)) FT[i] += x;
  return;
}
int Sum(int i)
{
  int ret = 0;
  for(; i; i -= i & (-i)) ret += FT[i];
  return ret;
}
void EDFS(int node, int parent = 0)
{
  L[node] = ++glob;
  for(int i = 0; i < (VG[node].size() - 1); i++) if(VG[node][i] == parent) swap(VG[node][i], VG[node].back());
  if(parent) VG[node].pop_back();
  UP[0][node] = parent;
  for(int i = 1; UP[i - 1][node]; i++) UP[i][node] = UP[i - 1][UP[i - 1][node]];
  for(int x : VG[node]) {DIST[x] = DIST[node] + 1; EDFS(x, node);}
  R[node] = glob;
  return;
}
int LCA(int u, int v)
{
  if(DIST[u] > DIST[v]) swap(u, v);
  for(int i = 16; i >= 0; i--) if(UP[i][v] && (DIST[UP[i][v]] >= DIST[u])) v = UP[i][v];
  if(u == v) return u;
  for(int i = 16; i >= 0; i--) if(UP[i][u] && UP[i][v] && (UP[i][u] ^ UP[i][v])) {u = UP[i][u]; v = UP[i][v];}
  return UP[0][u];
}
int BS(int u, int v)
{
  if((L[u] > L[v]) || (R[u] < R[v])) exit(333);
  int l = 0, r = VG[u].size() - 1, s, ret;
  while(l <= r)
  {
    s = (l + r) >> 1;
    if(L[VG[u][s]] <= L[v]) {l = s + 1; ret = s;}
    else r = s - 1;
  }
  return VG[u][ret];
}
void DPDFS(int node)
{
  for(int x : VG[node])
  {
    DPDFS(x);
    DP[1][node] += DP[0][x];
  }
  DP[0][node] = DP[1][node];
  for(auto a : V[node])
  {
//    cout << node << ":\n";
    int dp = DP[1][node] + a[2];
    if(a[0] ^ node)
    {
      dp -= DP[0][BS(node, a[0])];
      dp += Sum(L[a[0]]) + DP[1][a[0]];
//      cout << a[0] << ' ' << BS(node, a[0]) << ' ' << dp << '\n';
    }
    if(a[1] ^ node)
    {
      dp -= DP[0][BS(node, a[1])];
      dp += Sum(L[a[1]]) + DP[1][a[1]];
//      cout << a[1] << ' ' << BS(node, a[1]) << ' ' << dp << '\n';
    }
//    cout << dp << '\n';
    DP[0][node] = max(dp, DP[0][node]);
  }
//  cout << node << ' ' << DP[0][node] << ' ' << DP[1][node] << '\n';
  for(int x : VG[node])
  {
    Add(L[x], DP[1][node] - DP[0][x]);
    Add(R[x] + 1, DP[0][x] - DP[1][node]);
  }
  return;
}
int main()
{
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> N;
  int u, v, w;
  for(int i = 1; i < N; i++)
  {
    cin >> u >> v;
    VG[u].push_back(v);
    VG[v].push_back(u);
  }
  EDFS(1);
  cin >> M;
  for(int i = 1; i <= M; i++)
  {
    cin >> u >> v >> w;
    V[LCA(u, v)].push_back({u, v, w});
  }
  DPDFS(1);
  cout << DP[0][1] << '\n';

  return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...