Submission #1296859

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296859		danglayloi1	Election Campaign (JOI15_election_campaign)	C++20	100 / 100	118 ms	29504 KiB

election_campaign

#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=2e5+5;
const int LG=18;
int n, h[nx], up[nx][LG], m, dp[nx], f[nx], st[nx], en[nx], tim=0, bit[nx];
vector<int> adj[nx];
vector<pair<ii, int>> ve[nx];
void add(int x, int val)
{
    for(; x <= 2*n; x+=x&-x)
        bit[x]+=val;
}
int get(int x)
{
    int res=0;
    for(; x > 0; x-=x&-x)
        res+=bit[x];
    return res;
}
void dfs(int u)
{
    st[u]=++tim;
    for(int v:adj[u])
    {
        if(v==up[u][0]) continue;
        h[v]=h[u]+1;
        up[v][0]=u;
        for(int i = 1; i < LG; i++)
            up[v][i]=up[up[v][i-1]][i-1];
        dfs(v);
    }
    en[u]=++tim;
}
int jump(int u, int k)
{
    if(k<0) return u;
    for(int i = 0; i < LG; i++)
        if(k>>i&1) u=up[u][i];
    return u;
}
int lca(int u, int v)
{
    if(h[u]<h[v]) swap(u, v);
    u=jump(u, h[u]-h[v]);
    if(u==v) return u;
    for(int i = LG-1; i >= 0; i--)
        if(up[u][i]!=up[v][i])
            u=up[u][i], v=up[v][i];
    return up[u][0];
}
void go(int u)
{
    f[u]=0;
    for(int v:adj[u])
    {
        if(v==up[u][0]) continue;
        go(v);
        f[u]+=dp[v];
    }
    dp[u]=f[u];
    for(auto it:ve[u])
    {
        int l, r;
        tie(l, r)=it.fi;
        if(h[l]>h[r]) swap(l, r);
        int l1=jump(l, h[l]-h[u]-1);
        int r1=jump(r, h[r]-h[u]-1);
        if(l==r) dp[u]=max(dp[u], f[u]+it.se);
        else if(l==u) dp[u]=max(dp[u], f[u]-dp[r1]+it.se+get(st[r])+f[r]);
        else dp[u]=max(dp[u], f[u]-dp[l1]-dp[r1]+it.se+get(st[l])+get(st[r])+f[l]+f[r]);
    }
    for(int v:adj[u])
        if(v!=up[u][0])
            add(st[v], f[u]-dp[v]), add(en[v], dp[v]-f[u]);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i = 1; i < n; i++)
    {
        int u, v;
        cin>>u>>v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    dfs(1);
    cin>>m;
    while(m--)
    {
        int u, v, c;
        cin>>u>>v>>c;
        int p=lca(u, v);
        ve[p].push_back({{u, v}, c});
    }
    go(1);
    // for(int i = 1; i <= n; i++)
    //     cout<<dp[i]<<' ';
    cout<<dp[1];
}

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