Submission #1356748

#TimeUsernameProblemLanguageResultExecution timeMemory
1356748NewtonabcElection Campaign (JOI15_election_campaign)C++20
100 / 100
160 ms28448 KiB
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
ll fw[N],dp[N];
vector<int> adj[N];
vector<tuple<int,int,ll>> f[N];
int ti=1,in[N],out[N],d[N][18],dep[N];
void upd(int i,int val){for(;i<N;i+=i&-i) fw[i]+=val;}
int qry(int i){ll s=0; for(;i;i-=i&-i) s+=fw[i]; return s;}
int lca(int u,int v){
    if(dep[u]>dep[v]) swap(u,v);
    for(int i=17;i>=0;i--) if(dep[d[v][i]]>=dep[u]) v=d[v][i];
    if(u==v) return u;
    for(int i=17;i>=0;i--) if(d[u][i]!=d[v][i]) u=d[u][i],v=d[v][i];
    return d[u][0];
}
void dfs(int u,int p){
    in[u]=ti++;
    d[u][0]=p;
    for(auto v:adj[u]){
        if(v==p) continue;
        dep[v]=dep[u]+1;
        dfs(v,u);
    }
    out[u]=ti;
}
void efs(int u,int p){
    ll sum=0;
    for(auto v:adj[u]){
        if(v==p) continue;
        efs(v,u);
        sum+=dp[v];
    }
    ll add=0;
    for(auto [x,y,w]:f[u]){
        ll ta=qry(in[x])-qry(in[u]);
        ll tb=qry(in[y])-qry(in[u]);
        add=max(add,w+ta+tb);
    }
    dp[u]=sum+add;
    upd(in[u],-dp[u]+sum);
    upd(out[u],dp[u]-sum);
}
int main(){
    int n; cin>>n;
    for(int i=0;i<n-1;i++){
        int u,v; cin>>u >>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1,1);
    for(int i=1;i<18;i++) for(int j=1;j<=n;j++) d[j][i]=d[d[j][i-1]][i-1];
    int m; cin>>m;
    for(int i=0;i<m;i++){
        int u,v; ll w; cin>>u >>v >>w;
        f[lca(u,v)].push_back({u,v,w});
    }
    efs(1,1);
    cout<<dp[1];
}
#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...