Submission #1217251

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217251		AlgorithmWarrior	Election Campaign (JOI15_election_campaign)	C++20	100 / 100	160 ms	26588 KiB

election_campaign

#include <bits/stdc++.h>

using namespace std;

int const NMAX=100005;
int const LOG=20;
int n,m;
vector<int>tree[NMAX];

void read(){
    cin>>n;
    int i;
    for(i=1;i<n;++i){
        int u,v;
        cin>>u>>v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
}

int lift[NMAX][LOG];
int h[NMAX];
int tin[NMAX],tout[NMAX];

void dfs(int nod){
    int i;
    static int time=0;
    tin[nod]=++time;
    for(i=1;i<LOG;++i)
        lift[nod][i]=lift[lift[nod][i-1]][i-1];
    for(auto fiu : tree[nod])
        if(fiu!=lift[nod][0]){
            lift[fiu][0]=nod;
            h[fiu]=h[nod]+1;
            dfs(fiu);
        }
    tout[nod]=time;
}

struct path{
    int u,v,cost;
}paths[NMAX];
vector<int>ids[NMAX];

int lca(int u,int v){
    if(h[u]<h[v])
        swap(u,v);
    int dh=h[u]-h[v];
    int i;
    for(i=0;i<LOG;++i)
        if(dh&(1<<i))
            u=lift[u][i];
    if(u==v)
        return u;
    for(i=LOG-1;i>=0;--i)
        if(lift[u][i]!=lift[v][i]){
            u=lift[u][i];
            v=lift[v][i];
        }
    return lift[u][0];
}

void read_paths(){
    cin>>m;
    int i;
    for(i=1;i<=m;++i){
        int u,v,cost;
        cin>>u>>v>>cost;
        paths[i]={u,v,cost};
        ids[lca(u,v)].push_back(i);
    }
}

int ub(int x){
    return x&(-x);
}

struct fenwick_tree{
    long long v[NMAX];
    void upd(int pos,long long val){
        while(pos<=n){
            v[pos]+=val;
            pos+=ub(pos);
        }
    }
    long long qry(int pos){
        long long s=0;
        while(pos){
            s+=v[pos];
            pos-=ub(pos);
        }
        return s;
    }
}aib;

void maxself(long long& x,long long val){
    if(x<val)
        x=val;
}

long long solve(int nod){
    long long sum=0;
    for(auto fiu : tree[nod])
        if(fiu!=lift[nod][0])
            sum+=solve(fiu);
    long long ans=0;
    for(auto id : ids[nod]){
        auto [u,v,cost]=paths[id];
        maxself(ans,cost+aib.qry(tin[u])+aib.qry(tin[v]));
    }
    aib.upd(tin[nod],-ans);
    aib.upd(tout[nod]+1,ans);
    return ans+sum;
}

int main()
{
    read();
    dfs(1);
    read_paths();
    cout<<solve(1);
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 30 / 30
• Subtask 5: 10 / 10
• Subtask 6: 40 / 40