Submission #1321586

#TimeUsernameProblemLanguageResultExecution timeMemory
1321586wangzhiyi33Election Campaign (JOI15_election_campaign)C++20
100 / 100
364 ms38380 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define ii pair<int,int>
#define fir first
#define sec second
const int maxn=1e5;
int n;
vector<int>adj[maxn+2];
int bin[maxn+2][20];
int in[maxn+2],out[maxn+2],dep[maxn+2];
int cnt=0;

void dfs(int cur,int par){
    in[cur]=++cnt;
    bin[cur][0]=par; dep[cur]=dep[par]+1;

    for(auto x : adj[cur]){
        if(x==par)continue;
        dfs(x,cur);
    }
    out[cur]=cnt;
}

int lca(int a,int b){
    if(dep[a]<dep[b])swap(a,b);
    int slsh=dep[a]-dep[b];
    for(int q=19;q>=0;q--){
        if(slsh>=(1<<q)){
            slsh-=(1<<q);
            a=bin[a][q];
        }
    }

    if(a==b)return a;
    for(int q=19;q>=0;q--){
        if(bin[a][q]!=bin[b][q]){
            a=bin[a][q],b=bin[b][q];
        }
    }
    return bin[a][0];
}

vector<array<int,3> >isi[maxn+2];
int dp[maxn+2][2];

int fen[maxn+2];

void add(int idx,int val){
    for(int q=idx;q<=maxn;q+=(q & (-q))){
        fen[q]+=val;
    }
}

int query(int idx){
    int tot=0;
    for(int q=idx;q>0;q-=(q & (-q))){
        tot+=fen[q];
    }
    return tot;
}

void solve(int cur,int par){
    for(auto x : adj[cur]){
        if(x==par)continue;
        solve(x,cur);
        dp[cur][0]+=max(dp[x][0],dp[x][1]);
    }
    dp[cur][1]=dp[cur][0];

    for(auto [u,v,w] : isi[cur]){
        int tot=dp[cur][0]+w;
        tot+=query(in[u]);
        tot+=query(in[v]);
        // if(cur==5){
        //     cout<<query(in[u])<<" "<<query(in[v])<<" "<<u<<" "<<v<<endl;
        // }
        dp[cur][1]=max(dp[cur][1],tot);
    }

    int slsh=dp[cur][0]-dp[cur][1];
    add(in[cur],slsh);
    add(out[cur]+1,-slsh);
}

signed main(){
    cin>>n;
    for(int q=1;q<n;q++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1,0);
    for(int q=1;q<20;q++){
        for(int w=1;w<=n;w++){
            bin[w][q]=bin[bin[w][q-1]][q-1];
        }
    }

    int k;
    cin>>k;
    for(int q=1;q<=k;q++){
        int u,v,w;
        cin>>u>>v>>w;
        isi[lca(u,v)].push_back({u,v,w});
    }
    solve(1,0);

    int ans=0;
    for(int q=1;q<=n;q++){
        ans=max({ans,dp[q][0],dp[q][1]});
       // cout<<dp[q][0]<<" "<<dp[q][1]<<endl;
    }
    cout<<ans<<endl;
}
#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...