Submission #198651

#	Time	Username	Problem	Language	Result	Execution time	Memory
198651		osaaateiasavtnl	Election Campaign (JOI15_election_campaign)	C++14	20 / 100	1088 ms	38180 KiB

election_campaign

#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;
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];
    tin[u] = timer++;        
    for (int v : g[u]) 
        if (v != p)
            dfs(v, u);
    tout[u] = timer++;
}   
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];  
int getprev(int u, int v) {
    if (u == v)
        return 0;
    for (int i = LG - 1; i >= 0; --i) 
        if (!anc(to[u][i], v))
            u = to[u][i];
    return dp[u];
}   
struct Quer {
    int u, v, c;
} d[N];  
int get(int u, int p) {
    int ans = 0, last = -1;
    while (u != p) {
        for (int v : g[u]) {
            if (v != to[u][0] && v != last) {
                ans += dp[v];
            }   
        }   
        last = u;
        u = to[u][0];
    }   
    return ans;
}   
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 - getprev(d[i].u, u) - getprev(d[i].v, u) + d[i].c);
}
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';
}   

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