Submission #799401

#TimeUsernameProblemLanguageResultExecution timeMemory
799401futureElection Campaign (JOI15_election_campaign)C++17
100 / 100
195 ms32844 KiB
#include <bits/stdc++.h> using namespace std; const int N=1e5+5; int n,m; vector<int>g[N]; int tab[18][N]; int depth[N]; int pos=0; int in[N]; int out[N]; void DFS(int u,int par) { pos++; in[u]=pos; for(auto v:g[u]) if(v!=par) { tab[0][v]=u; depth[v]=depth[u]+1; DFS(v,u); } out[u]=pos; } void init() { depth[1]=1; DFS(1,0); for(int i=1; i<=17; i++) for(int j=1; j<=n; j++) tab[i][j]=tab[i-1][tab[i-1][j]]; } int LCA(int u,int v) { if(depth[u]<depth[v])swap(u,v); for(int i=17; i>=0; i--)if(depth[tab[i][u]]>=depth[v])u=tab[i][u]; if(u==v)return u; for(int i=17; i>=0; i--)if(tab[i][u]!=tab[i][v]) { v=tab[i][v]; u=tab[i][u]; } return tab[0][u]; } long long dp[N]; struct event { int u,v,c; }; vector<event>save[N]; long long aib[N]; void add(int i, int x) { while (i <N) { aib[i] += x; i += i & (-i); } } long long get(int i) { int sol = 0; while (i) { sol += aib[i]; i -= i & (-i); } return sol; } long long sum[N]; void DFS_ans(int u,int par) { for(auto v:g[u]) if(v!=par) { DFS_ans(v,u); sum[u]+=dp[v]; } dp[u]=sum[u]; for(auto v:save[u]) { dp[u]=max(dp[u],get(in[v.u])+get(in[v.v])+v.c+sum[u]); } add(in[u],sum[u]-dp[u]); add(out[u]+1,dp[u]-sum[u]); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 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); } init(); cin>>m; while(m--) { int u,v,c; cin>>u>>v>>c; save[LCA(u,v)].push_back({u,v,c}); } DFS_ans(1,0); cout<<dp[1]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...