Submission #1249385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249385		nguyenhuythach	Election Campaign (JOI15_election_campaign)	C++20	100 / 100	120 ms	40008 KiB

election_campaign

//y tuong cua from khanh nguyen
#include<bits/stdc++.h>
#include<algorithm>
#include<random>
#include<chrono>
#include<cstdlib>
#include<ctime>
#include<numeric>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<iomanip>
#define int long long
#define ll long long
#define L LLONG_MAX
#define fi first
#define se second
#define pii pair<int,int>
#define sz(a) ((int)a.size())
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define REP(i,k,j) for(int i=k;i>=j;i--)
#define FORD(i,a) for(auto i:a)
#define rngdcl mt19937_64 rng(chrono::steady_clock::now().time_asince_epoch().count())
#define random(l,r) ((l)+(rng()%(r-l+1)))
using namespace std;
struct dt
{
    int u,v,c;
};

const int nmax=1e5+1;
int n,m,t=0;
vector<int> adj[nmax];
vector<dt> qr[nmax];
int depth[nmax],jump[nmax][20],f[nmax],tin[nmax],tout[nmax];

void pre_dfs(int u,int v)
{
    tin[u]=++t;
    for(auto i:adj[u])
    {
        if(i==v) continue;
        depth[i]=depth[u]+1;
        pre_dfs(i,u);
        jump[i][0]=u;
    }
    tout[u]=t;
}

void buildjump()
{
    FOR(i,1,log2(n)) FOR(u,1,n) jump[u][i]=jump[jump[u][i-1]][i-1];
}

int lca(int u,int v)
{
    if(depth[v]<depth[u]) swap(u,v);
    int dis=depth[v]-depth[u];
    REP(i,log2(n)+1,0) if(dis&(1<<i)) v=jump[v][i];
    if(u==v) return u;
    REP(i,log2(n)+1,0)
    {
        if(jump[v][i]==0 || jump[u][i]==0) continue;
        if(jump[u][i]!=jump[v][i])
        {
            u=jump[u][i];
            v=jump[v][i];
        }
    }
    return jump[u][0];
}

struct BIT
{
    vector<int> tree;
    int n;
    
    BIT (int N)
    {
        n=N;
        tree.resize(n+4,0);
    }
    
    void update(int x,int val)
    {
        while(x<=n)
        {
            tree[x]+=val;
            x+=(x&-x);
        }
    }
    
    int get(int x)
    {
        int ans=0;
        while(x>0)
        {
            ans+=tree[x];
            x-=(x&-x);
        }
        return ans;
    }
} res(0),total(0);

void input()
{
    cin >> n;
    FOR(i,1,n-1)
    {
        int u,v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    pre_dfs(1,0);
    buildjump();
    cin >> m;
    FOR(i,1,m)
    {
        int u,v,c; cin >> u >> v >> c;
        int LCA=lca(u,v);
        qr[LCA].push_back({u,v,c});
    }
}

void dfs(int u,int v)
{
    int ans=0;
    FORD(i,adj[u])
    {
        if(i==v) continue;
        dfs(i,u);
        ans+=res.get(tin[i]);
    }
    
    FORD(i,qr[u])
    {
        int save=i.c+f[u]+total.get(tin[i.u])+total.get(tin[i.v])-res.get(tin[i.u])-res.get(tin[i.v]);
        ans=max(ans,save);
    }
    res.update(tin[u],ans);
    res.update(tout[u]+1,-ans);
    f[v]+=ans;
    total.update(tin[u],f[u]);
    total.update(tout[u]+1,-f[u]);
}

void solve()
{
    res=BIT(n);
    total=BIT(n);
    dfs(1,0);
    cout << res.get(1);
}

signed main()
{
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    input();
    solve();
}

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