Submission #1168102

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168102		sitablechair	Election Campaign (JOI15_election_campaign)	C++20	100 / 100	109 ms	33352 KiB

election_campaign

#include <bits/stdc++.h>

#define ll long long
#define ldb long double
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define F "TASK"
#define fio freopen(F".INP","r",stdin);freopen(F".OUT","w",stdout);

using namespace std;

const int N=1e5+3;

int n,m,siz[N],d[N],par[17][N],tin[N],tout[N],tdfs=0;
int cH[N],cId[N],pos[N],curChain=0,curPos=0,chain[N];
ll bit[N],dp[N],dp1[N];
vector<int> g[N];
vector<pair<int,int>> in[N];
vector<pair<pair<int,int>,int>> in1[N];
ll query(int x) {
    ll ans=0;
    while(x>0) {
        ans+=bit[x];
        x-=x&(-x);
    }
    return ans;
}
void update(int x,int y) {
    if (x==0) return;
    while(x<=n) {
        bit[x]+=y;
        x+=x&(-x);
    }
}
void predfs(int u,int p=0) {
    tin[u]=++tdfs;
    siz[u]=1;
    for(auto v: g[u])
        if (v!=p) {
            d[v]=d[u]+1;
            par[0][v]=u;
            For(i,1,16)
                par[i][v]=par[i-1][par[i-1][v]];
            predfs(v,u);
            siz[u]+=siz[v];
        }
    tout[u]=tdfs;
}
void hld(int u,int p=0) {
    int big=-1,bsz=-1;
    chain[++curPos]=u;
    pos[u]=curPos;
    cId[u]=curChain;
    if (!cH[cId[u]])
        cH[curChain]=u;
    for(auto v: g[u])
        if (v!=p && bsz<siz[v]) big=v,bsz=siz[v];
    if (big!=-1)
        hld(big,u);
    for(auto v: g[u])
        if (v!=p && v!=big) {
            curChain++;
            hld(v,u);
        }
}
int lca(int u,int v) {
    if (d[u]<d[v]) swap(u,v);
    int dd=d[u]-d[v];
    For(i,0,17)
        if (dd>>i&1) u=par[i][u];

    if (u==v) return u;
    ForD(i,16,0)
        if (par[i][u]!=par[i][v]) u=par[i][u],v=par[i][v];
    return par[0][u];
}
ll qr(int u,int v) {
    if (u==v) return dp1[v];
    int tmp=v;
    ll ans=0;
    ans+=dp1[v];

    v=par[0][v];
    while(cId[v]!=cId[u]) {
        ans+=query(pos[v]-1)-query(pos[cH[cId[v]]]-1);
        ans+=dp1[v]-dp[tmp];
        tmp=cH[cId[v]];
        v=par[0][cH[cId[v]]];
    }
    ans+=query(pos[v]-1)-query(pos[u]-1);
    ans+=dp1[v]-dp[tmp];
    return ans;
}
void dfs(int u,int p=0) {
    int big=-1,bsz=-1;
    for(auto v: g[u])
        if (v!=p) {
            if (siz[v]>bsz) bsz=siz[v],big=v;
            dfs(v,u);
            dp1[u]+=dp[v];
        }
    dp[u]=dp1[u];
    if (big!=-1) update(pos[u],dp1[u]-dp[big]);
    //if (u==5) cout << "AA: " << qr(5,2)+qr(5,6)-dp[u]+9 << endl;
    for(auto el: in[u]) {
        dp[u]=max(dp[u],qr(u,el.ff)+el.ss);
    }
    for(auto el: in1[u]) {
        //if (u==5) cout << qr(u,el.ff.ff)+qr[u,el.ff.ss]-dp1[u] << endl;
        dp[u]=max(dp[u],qr(u,el.ff.ff)+qr(u,el.ff.ss)-dp1[u]+el.ss);
    }
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    For(i,1,n-1) {
        int u,v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    predfs(1);
    hld(1);

    cin >> m;
    For(i,1,m) {
        int u,v,w;
        cin >> u >> v >> w;
        if (d[u]<d[v]) swap(u,v);
        if (lca(u,v)==v) {
            in[v].pb({u,w});
        } else {
            in1[lca(u,v)].pb({{u,v},w});
        }
    }
    dfs(1);

    cout << dp[1];
    return 0;
}
/*
7
3 4
6 5
2 7
1 5
7 5
4 5
5
4 3 10
5 6 5
2 6 9
7 2 2
1 3 8
*/

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