Submission #198653

#TimeUsernameProblemLanguageResultExecution timeMemory
198653osaaateiasavtnlElection Campaign (JOI15_election_campaign)C++14
100 / 100
353 ms44792 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
const int N = 1e5 + 7, LG = 20;
vector <int> g[N];
vector <int> mem[N];
int to[N][LG];
int tin[N], tout[N], timer = 0;

int in = 0, out = 0, in_pos[N], out_pos[N], r[N];

void dfs(int u, int p) {
    to[u][0] = p;
    for (int i = 1; i < LG; ++i)
        to[u][i] = to[to[u][i - 1]][i - 1];
    r[u] = out - 1;
    tin[u] = timer++;        
    in_pos[u] = in++;
    for (int v : g[u]) 
        if (v != p)
            dfs(v, u);
    tout[u] = timer++;
    out_pos[u] = out++;
}   
bool anc(int u, int v) {
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}   
int lca(int u, int v) {
    if (anc(u, v))
        return u;
    for (int i = LG - 1; i >= 0; --i) 
        if (!anc(to[u][i], v))
            u = to[u][i];
    return to[u][0];
}
int dp[N];  
struct Quer {
    int u, v, c;
} d[N];  

void add(int i, int x, int *f) {
    for (; i < N; i |= i + 1)
        f[i] += x;
}   
int get(int i, int *f) {
    int ans = 0;
    for (; i >= 0; i &= i + 1, --i)
        ans += f[i];    
    return ans;
}   
int get(int l, int r, int *f) {
    return get(r, f) - get(l - 1, f);
}   

int in_f[N], out_f[N];

int get(int u) {
    return get(in_pos[u], in_f) - get(r[u], out_f);
}   
int get(int u, int p) {
    return get(u) - get(p);
}   
void solve(int u, int p) {
    int sum = 0;
    for (int v : g[u])
        if (v != p) {
            solve(v, u);
            dp[u] += dp[v];
            sum += dp[v];
        }
    for (int i : mem[u]) 
        dp[u] = max(dp[u], get(d[i].u, u) + get(d[i].v, u) + sum + d[i].c);
    sum -= dp[u];
    add(in_pos[u], sum, in_f);
    add(out_pos[u], sum, out_f);
}
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    int n;
    cin >> n;    
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].app(v); g[v].app(u);
    }   
    dfs(1, 1);
    int m;
    cin >> m;
    for (int i = 0; i < m; ++i) {
        cin >> d[i].u >> d[i].v >> d[i].c;
        mem[lca(d[i].u, d[i].v)].app(i);                        
    }
    solve(1, 1);
    #ifdef HOME
    for (int i = 1; i <= n; ++i)
        cout << dp[i] << ' ';
    cout << '\n';
    #endif
    cout << dp[1] << '\n';
}   
#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...