제출 #1342661

#제출 시각아이디문제언어결과실행 시간메모리
1342661Born_To_LaughElection Campaign (JOI15_election_campaign)C++17
100 / 100
92 ms21912 KiB
// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(AC) AC.begin(), AC.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
[[maybe_unused]] const int MOD = 998244353, INF = 1e9 + 7;

struct Fen
{
    int n;
    vector<int> bit;
    void init(int len){
        n = len;
        bit.assign(n + 1, 0);
    }
    void upd(int pos, int val){
        for(; pos<=n; pos += pos & -pos) bit[pos] += val;
    }
    int qr(int pos){
        int ans = 0;
        for(; pos>0; pos -= pos & -pos) ans += bit[pos];
        return ans;
    }
    int qr(int l, int r){
        return qr(r) - qr(l - 1);
    }
};

const int maxn = 1e5 + 10;
Fen ft;
int tin[maxn], head[maxn], parr[maxn], chain[maxn];
int sz[maxn], big[maxn], dep[maxn];
int dp[maxn];
pair<pair<int, int>, int> plan[maxn];
vector<int> adj[maxn];
vector<int> lip[maxn]; // sth[i] = list of index of plans have lca = i;
int n, m;
int id = 0, cur = 1;

void pre_dfs(int a, int par){
    sz[a] = 1;
    for(auto &elm: adj[a]){
        if(elm == par) continue;
        parr[elm] = a;
        dep[elm] = dep[a] + 1;
        pre_dfs(elm, a);
        sz[a] += sz[elm];
        if(sz[elm] > sz[big[a]]) big[a] = elm;
    }
}
void hld(int a, int par, int root){
    tin[a] = ++id;
    head[a] = root;
    chain[a] = cur;

    if(big[a]) hld(big[a], a, root);

    for(auto &elm: adj[a]){
        if(elm == par || elm == big[a]) continue;
        cur++;
        hld(elm, a, elm);
    }
}
int lca(int a, int b){
    while(chain[a] != chain[b]){
        if(chain[a] < chain[b]) swap(a, b);
        a = parr[head[a]];
    }
    if(dep[a] > dep[b]) swap(a, b);
    return a;
}

int ope(int c, int i){
    int a = plan[i].fi.fi;
    int b = plan[i].fi.se;
    int ans = 0;
    while(chain[a] != chain[c]){
        if(big[a]) ans += dp[big[a]];
        ans += ft.qr(tin[head[a]], tin[a]);
        ans -= dp[head[a]];
        a = parr[head[a]];
    }
    while(chain[b] != chain[c]){
        if(big[b]) ans += dp[big[b]];
        ans += ft.qr(tin[head[b]], tin[b]);
        ans -= dp[head[b]];
        b = parr[head[b]];
    }
    if(dep[a] > dep[b]) swap(a, b);
    ans += ft.qr(tin[a], tin[b]);
    if(big[b]) ans += dp[big[b]];
    return ans;
}

void dfsdp(int a, int par){

    for(auto &elm: adj[a]){
        if(elm == par) continue;
        dfsdp(elm, a);
        dp[a] += dp[elm];
    }

    for(auto &i: lip[a]){
        dp[a] = max(dp[a], ope(a, i) + plan[i].se);
    }

    if(a == head[a] && a != 1){
        ft.upd(tin[parr[a]], dp[a]);
    }
}


void solve(){
    cin >> n;
    for(int i=1; i<n; ++i){
        int a, b;cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    cin >> m;
    for(int i=1; i<=m; ++i){
        cin >> plan[i].fi.fi >> plan[i].fi.se >> plan[i].se;
    }

    pre_dfs(1, -1);
    hld(1, -1, 1);

    ft.init(n);

    for(int i=1; i<=m; ++i){
        int c = lca(plan[i].fi.fi, plan[i].fi.se);
        lip[c].push_back(i);
    }

    dfsdp(1, -1);

    

    int ans = -INF;
    for(int i=1; i<=n; ++i) ans = max(ans, dp[i]);
    cout << ans << '\n';
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...