Submission #648548

#	Time	Username	Problem	Language	Result	Execution time	Memory
648548		BackNoob	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	228 ms	57932 KiB

election_campaign

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()

using namespace std;
const int mxN = 5e5 + 227;
const int inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;

template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}


struct FenwickTree{
	int n;
	vector<int> bit;
	FenwickTree(){}
	FenwickTree(int _n) {
		n = _n;
		bit.resize(n + 7, 0);
	}

	void update(int pos, int val)
	{
		for(; pos <= n; pos += pos & -pos) bit[pos] += val;
	}
	int getsum(int pos)
	{
		int res = 0;
		for(; pos > 0; pos -= pos & -pos) res += bit[pos];
		return res;
	}
	int getsum(int l, int r)
	{
		return getsum(r) - getsum(l - 1);
	}
} ft;

struct Query{
    int u, v, c;
};

int n;
int m;
int dp[mxN];
int sum[mxN];
int sta[mxN];
int fin[mxN];
int dep[mxN];
int par[mxN][LOG + 1];
vector<int> adj[mxN];
vector<Query> query[mxN];
int timer = 0;

void dfs_pre(int u, int p)
{
    sta[u] = ++timer;
    for(int v : adj[u]) {
        if(v == p) continue;
        dep[v] = dep[u] + 1;
        par[v][0] = u;
        dfs_pre(v, u);
    }
    fin[u] = timer;
}

int getlca(int u, int v)
{
    if(dep[u] < dep[v]) swap(u, v);

    for(int j = LOG; j >= 0; j--) if(dep[par[u][j]] >= dep[v]) u = par[u][j];

    if(u == v) return u;

    for(int j = LOG; j >= 0; j--) {
        if(par[u][j] != par[v][j]) {
            u = par[u][j];
            v = par[v][j];
        }
    }
    return par[u][0];
}

void dfs(int u, int p)
{
    vector<pair<int, int>> val;
    int ans = 0;
    for(int v : adj[u]) {
        if(v == p) continue;
        dfs(v, u);
        ans += dp[v];
        val.pb({sta[v], dp[v]});
    }

    sum[u] = ans;
    dp[u] = ans;

    sort(all(val));

    for(auto it : query[u]) {
        int newval = ans + it.c + ft.getsum(sta[it.u]) + ft.getsum(sta[it.v]);
//        int x = it.u;
//        int y = it.v;

//        while(x != u) {
//            newval += sum[x] - dp[x];
//            x = par[x][0];
//        }
//        while(y != u) {
//            newval += sum[y] - dp[y];
//            y = par[y][0];
//        }



//        int newval = ans + it.c;
//        if(it.u != u) {
//            int p = upper_bound(all(val), make_pair(sta[it.u], inf)) - val.begin();
//            newval -= val[p - 1].se;
//            newval += sum[it.u];
//        }
//        if(it.v != u) {
//            int p = upper_bound(all(val), make_pair(sta[it.v], inf)) - val.begin();
//            newval -= val[p - 1].se;
//            newval += sum[it.v];
//        }
        maximize(dp[u], newval);
    }
    ft.update(sta[u], sum[u] - dp[u]);
    ft.update(fin[u] + 1, dp[u] - sum[u]);
}

void solve()
{
    cin >> n;
    for(int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }

    par[1][0] = 1;
    dfs_pre(1, -1);
    for(int j = 1; j <= LOG; j++)
    for(int i = 1; i <= n; i++)
        par[i][j] = par[par[i][j - 1]][j - 1];

    cin >> m;
    for(int i = 1; i <= m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        int lca = getlca(u, v);
        query[lca].pb({u, v, c});
    }

    ft = FenwickTree(n);
    dfs(1, -1);
    int res = 0;
    for(int i = 1; i <= n; i++) maximize(res, dp[i]);
    cout << res;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(TASK".inp" , "r" , stdin);
    //freopen(TASK".out" , "w" , stdout);

    int tc = 1;
    //cin >> tc;
    while(tc--) {
    	solve();
    }
    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