Submission #1298531

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298531		Minbaev	Election Campaign (JOI15_election_campaign)	C++20	Compilation error	0 ms	0 KiB

election_campaign

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define pb      push_back
#define all(x)  x.begin(),x.end()
#define ar      array
#define int 	long long 

template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}

template <class T> using ste = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

const long long inf = 3e18 + 7;
const int mod = 1000000007; 
const int md = 998244353;  
const int N = 3e5 + 5;

struct Bit {
    vector<int> b, b2;
    int n;

    Bit(int n) {
        this->n = n + 1;
        b.assign(n + 1, 0);
        b2.assign(n+1, 0);
    }

    void add(vector<int>&b, int idx, int x){
        while(idx <= n){
            b[idx] += x;
            idx += idx & -idx;
        }
    }

    void upd(int l, int r, int x){
		if(r < l)return;
        add(b, l, x);
        add(b, r+1, -x);
        add(b2, l, x*(l-1));
        add(b2, r+1, -x*r);
    }

    int sum(vector<int>&b, int idx){
        int res = 0;
        while(idx > 0){
            res += b[idx];
            idx -= idx & -idx;
        }
        return res;
    }

    int pref(int idx){
        return sum(b, idx) * idx - sum(b2, idx);
    }

    int get(int l, int r){                  
        return pref(r) - pref(l-1);
    }
};

int n,m,k;
vector<int>g[N], tin(N), tout(N), dp(N), sum(N), sub(N), id(N), anc(N);
vector<ar<int,3>>dir[N];
vector<ar<int,5>> unin[N];
vector<vector<int>>p(N, vector<int>(20));
int timer;

Bit t(N), t2(N);

void dfs(int x, int pr){
	sub[x] = 1;
	tin[x] = ++timer;
	p[x][0] = pr;
	for(int i = 1;i<20;i++)
		p[x][i] = p[p[x][i-1]][i-1];
	
	for(auto to : g[x]){
		if(to == pr)continue;
		dfs(to, x);
		sub[x] += sub[to];
	}
	
	tout[x] = ++timer;
}

bool is(int a, int b){
	return tin[a] <= tin[b] && tout[b] <= tout[a];
}

void hld(int x, int pr, int a){
	anc[x] = a;
	id[x] = ++timer;
	int u = -1;
	for(auto to : g[x]){
		if(to == pr)continue;
		if(u == -1)u = to;
		else if(sub[to] > sub[u])u = to;
	}
	
	if(u != -1){
		hld(u, x, a);
	}
	
	for(auto to : g[x]){
		if(to == pr || to == u)continue;
		hld(to, x, to);
	}
}

long long path(int a, int b, Bit &ts){
    long long res = 0;
    while(anc[a] != anc[b]){               
        res += ts.get(id[anc[a]], id[a]);  
        a = p[anc[a]][0];                  
    }
    
    res += ts.get(id[b], id[a]);
    return res;
}


int lca(int a, int b){
    if(is(a,b)) return a;
    if(is(b,a)) return b;
    for(int i = 19; i >= 0; --i){
        if(!is(p[a][i], b)) a = p[a][i];
    }
    return p[a][0];
}

int lca2(int a, int b){
	for(int i = 19;i>=0;i--){
		if(!is(p[a][i], b)){
			a = p[a][i];
		}
	}
	return a;
}

void ans(int x, int pr){
	for(auto to : g[x]){
		if(to == pr)continue;
		ans(to, x);
		dp[x] += dp[to];
		sum[x] += dp[to];
	}
	
	for(auto [a, b, c] : dir[x]){
		int sum2 = 0;
		if(a != b)sum2 = path(b, a, t) - path(b, lca2(b, a), t2);
		else sum2 = sum[b];
		umax(dp[x], sum[x] - dp[a] + sum2 + c);
	}
	
	for(auto [a_, b_, a, b, c] : unin[x]){
		int sum2 = 0;
		if(a != a_)sum2 += path(a, a_, t) - path(a, lca2(a, a_), t2);
		else sum2 += sum[a];
		
		if(b != b_)sum2 += path(b, b_, t) - path(b, lca2(b, b_), t2);
		else sum2 += sum[b];
		umax(dp[x], sum[x] - dp[a_] - dp[b_] + sum2 + c);
	}
	
	t.upd(id[x], id[x], sum[x]);
	t2.upd(id[x], id[x], dp[x]);
}

void solve(){
    
    cin >> n;
    for(int i = 2;i<=n;i++){
		int a,b;
		cin >> a >> b;
		g[a].pb(b);
		g[b].pb(a);
	}
	
	dfs(1, 1);
	timer = 0;
	hld(1, -1, 1);
	
	int q;
	cin >> q;
	while(q--){
		int a,b,c;
		cin >> a >> b >> c;
		if(tin[a] > tin[b])swap(a, b);
		int u = lca(a, b);
		if(is(a, b))
			dir[a].pb({lca2(b, a), b, c});
		else unin[u].pb({lca2(a, u), lca2(b, u), a, b, c});
	}
	
	//~ cout << lca2(10, 3) << " " << lca2(13, 4) << " " << lca2(5, 1) << "\n";
	
	//~ for(int i = 1;i<=n;i++){
		//~ cout << i << " : \n";
		//~ for(auto [a, b, c] : dir[i])cout << a << " " << b << " " << c << "\n";
		//~ for(auto [a, b, c, d, e] : unin[i])cout << a << " " << b << " " << c << " " << d << " " << e << "\n";
	//~ }
 	ans(1, 1);
    
    cout << dp[1] << "\n";
    
}
/*
15
1 2
2 3
3 4
4 5
6 7
2 7
2 8
8 9
10 3
3 11
12 14
13 14
4 15
14 4
5
1 5 25
7 9 10
10 11 10
12 15 10
15 13 115
*/
 signed main()
{
//  freopen("seq.in", "r", stdin);
//  freopen("seq.out", "w", stdout);
    ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
    int tt=1;//cin >> tt;
    while(tt--)solve();    

}