제출 #1156811

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1156811		Hamed_Ghaffari	Election Campaign (JOI15_election_campaign)	C++20	100 / 100	106 ms	26440 KiB

election_campaign

#include<bits/stdc++.h>
using namespace std;

#define mid ((l+r)>>1)
#define maxs(a,b) (a=max(a,b))
#define pb push_back

const int MXN = 1e5+5;
const int LOG = 17;

int n, m, A[MXN], B[MXN], C[MXN];
vector<int> g[MXN];
int par[LOG][MXN], stt[MXN], fnt[MXN], timer;

void dfs(int v) {
    stt[v] = timer++;
    for(int i=1; i<LOG; i++)
        par[i][v] = par[i-1][par[i-1][v]];
    for(int u : g[v])
        if(u^par[0][v])
            par[0][u] = v,
            dfs(u);
    fnt[v] = timer;
}
inline bool is_anc(int u, int v) { return stt[u]<=stt[v] && fnt[v]<=fnt[u]; }
inline int LCA(int u, int v) {
    if(is_anc(u,v)) return u;
    for(int i=LOG-1; i>=0; i--)
        if(par[i][u] && !is_anc(par[i][u], v))
            u = par[i][u];
    return par[0][u];
}

int fen[MXN];
inline void updx(int s, int e, int x) {
    for(++s; s<MXN; s+=s&-s) fen[s] += x;
    for(++e; e<MXN; e+=e&-e) fen[e] -= x;
}
inline int getx(int p) {
    int res=0;
    for(++p; p; p-=p&-p) res += fen[p];
    return res;
}

vector<int> Q[MXN];
int dp[MXN];

void DFS(int v) {
    int sum=0;
    for(int u : g[v])
        if(u^par[0][v])
            DFS(u),
            sum += dp[u];
    dp[v] = sum;
    for(int i : Q[v])
        maxs(dp[v], getx(stt[A[i]])+getx(stt[B[i]])+C[i]+sum);
    updx(stt[v], fnt[v], sum-dp[v]);
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n;
    for(int i=0, u,v; i<n-1; i++) {
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(1);
    int m;
    cin >> m;
    for(int i=1; i<=m; i++) {
        cin >> A[i] >> B[i] >> C[i];
        Q[LCA(A[i], B[i])].pb(i);
    }
    DFS(1);
    cout << dp[1] << '\n';
    return 0;
}

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