Submission #1130704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130704		ByeWorld	Election Campaign (JOI15_election_campaign)	C++20	0 / 100	1097 ms	30860 KiB

election_campaign

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<int,pii> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 1e5+10;
const int MAXA = 1e6;
const int INF = 1e18+10;
const int MOD = 1e9+7;
const int LOG = 21;
const ld EPS = 1e-12;
void chmx(int &a, int b){ a = max(a, b); }

int n, m, a[MAXN], b[MAXN], c[MAXN];
vector <int> tree[MAXN], adj[MAXN];
int dep[MAXN], sub[MAXN], par[MAXN], root[MAXN];

void bd(int nw, int pa){
    par[nw] = pa; dep[nw] = dep[pa]+1; sub[nw] = 1;
    for(auto nx : tree[nw]){
        if(nx==pa) continue;
        adj[nw].pb(nx);
        bd(nx, nw);
        sub[nw] += sub[nx];
    }
}
int tim, idx[MAXN];
void chain(int nw, int roo){
    idx[nw] = ++tim;
    root[nw] = roo;
    if(adj[nw].size() == 0) return;
    chain(adj[nw][0], roo);
    for(int i=1; i<adj[nw].size(); i++)
        chain(adj[nw][i], adj[nw][i]);
}
int LCA(int x, int y){
    while(root[x] != root[y]){
        if(dep[ root[x] ] > dep[ root[y] ]) swap(x,y);
        y = par[ root[y] ];
    }
    if(dep[x] > dep[y]) swap(x, y);
    return x;
}
struct seg {
    int st[2*MAXN];
    int que(int x){
        int te = 0;
        for(; x>=1; x-=(x&(-x))) te += st[x];
        return te;
    }
    void upd(int x, int p){
        for(; x<=2*MAXN-20; x+=(x&(-x))) st[x] += p;
    }
} A, B; // dp, sum of child

vector <int> vec[MAXN];
int dp[MAXN], val[MAXN];

int QUE(int x, int y){
    int ret = 0;
    while(y != x){
        ret -= dp[y]; ret += val[y];
        y = par[y];
    } 
    return ret;
}
void solve(int nw){
    for(auto nx : adj[nw]){
        solve(nx);
        chmx(dp[nw], dp[nx]);
        val[nw] += dp[nx];
    }
    for(auto id : vec[nw]){
        int x = a[id], y = b[id], cost = c[id];
        int te = QUE(nw, x) + QUE(nw, y) + val[nw];
        chmx(dp[nw], cost+te);
    }
}
signed main(){
    // ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i=1; i<=n-1; i++){
        int x,y; cin>>x>>y; tree[x].pb(y); tree[y].pb(x);
    }
    for(int i=1; i<=n; i++){
        if(adj[i].size()==0) continue;
        for(int j=1; j<adj[i].size(); j++)
            if(sub[adj[i][0]] < sub[adj[i][j]])
                swap(adj[i][0], adj[i][j]);
    }
    bd(1, 0); chain(1, 1);

    cin >> m;
    for(int i=1; i<=m; i++){
        cin >> a[i] >> b[i] >> c[i];
        int lca = LCA(a[i], b[i]);
        // cout << lca << " lc\n";
        vec[lca].pb(i);
    }
    solve(1);

    // for(int i=1; i<=n; i++){
    //     cout << i << ' ' << dp[i] << " dp\n";
    // }
    cout << dp[1] << '\n';
} 

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