Submission #962933

#	Time	Username	Problem	Language	Result	Execution time	Memory
962933		Unforgettablepl	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	174 ms	40788 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int modulo = 1e9+7;

int tim[100001];
int out[100001];
int par[100001][17];
int DP[100001][2];
int depth[100001];
int tree[100001];
vector<int> adj[100001];
vector<tuple<int,int,int>> paths[100001];
int c;

void add(int x,int k){
    while(x<=100000){
        tree[x]+=k;
        x+=x&-x;
    }
}

int getsum(int x){
    int ans = 0;
    while(x){
        ans+=tree[x];
        x-=x&-x;
    }
    return ans;
}

void dfs(int x,int p,int dep){
    par[x][0] = p;
    tim[x] = ++c;
    depth[x] = dep;
    for(int&i:adj[x])if(i!=p)dfs(i,x,dep+1);
    out[x] = c+1;
}

void dfs2(int x,int p){
    for(int&i:adj[x]){
        if(i==p)continue;
        dfs2(i,x);
        DP[x][0]+=DP[i][1];
    }
    DP[x][1]=DP[x][0];
    for(auto[end1,end2,cost]:paths[x]){
        DP[x][1] = max(DP[x][1],DP[x][0]+getsum(tim[end1])+getsum(tim[end2])+cost);
    }
    add(tim[x],DP[x][0]-DP[x][1]);
    add(out[x],DP[x][1]-DP[x][0]);
}

int lca(int a,int b){
    if(depth[a]>depth[b])swap(a,b);
    int target = depth[b]-depth[a];
    for(int bit=0;bit<17;bit++)if(target&(1<<bit))b=par[b][bit];
    for(int bit=16;bit>=0;bit--){
        if(par[a][bit]!=par[b][bit]){
            a = par[a][bit];
            b = par[b][bit];
        }
    }
    if(a==b)return a;
    return par[a][0];
}


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for(int i=1;i<n;i++){
        int a,b;cin>>a>>b;
        adj[a].emplace_back(b);
        adj[b].emplace_back(a);
    }
    dfs(1,0,1);
    for(int bit=1;bit<=16;bit++){
        for(int i=1;i<=n;i++){
            par[i][bit] = par[par[i][bit-1]][bit-1];
        }
    }
    int m;
    cin >> m;
    for(int i=1;i<=m;i++){
        int a,b,c;cin>>a>>b>>c;
        paths[lca(a,b)].emplace_back(a,b,c);
    }
    dfs2(1,0);
    cout << DP[1][1] << '\n';
}

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