Submission #619559

#	Time	Username	Problem	Language	Result	Execution time	Memory
619559		nohaxjustsoflo	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	347 ms	49936 KiB

election_campaign

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> order_set;
mt19937 mt_rand(chrono::high_resolution_clock::now().time_since_epoch().count());
//uniform_int_distribution<int> gen; ///(min, max)
//int random() {return gen(mt_rand);}
const int mxN=3e5+5;
const int mod=998244353;
const int mxlogN=20;
const int mxK=26;
const int inf=2e9;
const int K=600;


vector<int> adj[mxN];
int up[mxlogN][mxN], down[mxN], in[mxN], out[mxN], timer_;
vector<int> who[mxN];
void dfs(int i=1, int p=1, int d=0)
{
    up[0][i]=p, down[i]=d, in[i]=timer_++;
    who[d].push_back(i);
    for(int j=1; j<mxlogN; j++) up[j][i]=up[j-1][up[j-1][i]];
    for(int j:adj[i]) if(j!=p) dfs(j,i,d+1);
    out[i]=timer_;
}
int goup(int i, int k)
{
    for(int j=mxlogN-1; j>=0; j--) if(k&1<<j) i=up[j][i];
    return i;
}
int lca(int i, int j)
{
    if(down[i]<down[j]) swap(i,j);
    i=goup(i, down[i]-down[j]);
    if(i==j) return i;
    for(int k=mxlogN-1; k>=0; k--) if(up[k][i]!=up[k][j]) i=up[k][i], j=up[k][j];
    return up[0][i];
}
int sz;
void build(int n)
{
    sz=1;
    while(sz<n) sz<<=1;
}
ll sum[mxN];
void add(int l, int r, ll v, int i=0, int Lx=0, int Rx=sz)
{
    if(Rx<=l || Lx>=r) return;
    if(Lx>=l && Rx<=r)
    {
        sum[i]+=v;
        return;
    }
    int m=(Rx+Lx)/2;
    add(l,r,v,i*2+1,Lx,m);
    add(l,r,v,i*2+2,m,Rx);
}
ll dp2(int pos, int i=0, int Lx=0, int Rx=sz)
{
    if(Rx-Lx==1) return sum[i];
    int m=(Rx+Lx)/2;
    if(pos<m) return sum[i]+dp2(pos,i*2+1,Lx,m);
    else return sum[i]+dp2(pos,i*2+2,m,Rx);
}

struct qry
{
    int a,b,c;
};
vector<qry> qs[mxN];
int dp[mxN];
void solve(int i)
{
    int p=up[0][i];
    int ans=0;
    for(int j:adj[i])
    {
        if(j==p) continue;
        ans+=dp[j];
    }
    int ans2=ans;
    for(auto q:qs[i])
    {
        int a=q.a,b=q.b,c=q.c;
        int newans=dp2(in[a])+dp2(in[b])+c+ans;
        if(a!=i) newans-=dp[goup(a,down[a]-down[i]-1)];
        if(b!=i) newans-=dp[goup(b,down[b]-down[i]-1)];
        ans2=max(ans2,newans);
    }
    dp[i]=ans2;
    for(int j:adj[i])
    {
        if(j==p) continue;
        ans-=dp[j];
        add(in[j],out[j],ans);
        ans+=dp[j];
    }
    add(in[i],in[i]+1,ans);
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    build(n);
    for(int i=1; i<n; i++)
    {
        int u,v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs();
    int m; cin >> m;
    for(int i=0; i<m; i++)
    {
        int a,b,c; cin >> a >> b >> c;
        qs[lca(a,b)].push_back({a,b,c});
    }
    for(int d=n-1; d>=0; d--) for(int i:who[d]) solve(i);
    cout << dp[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