Submission #265037

#TimeUsernameProblemLanguageResultExecution timeMemory
265037GoolakhElection Campaign (JOI15_election_campaign)C++17
100 / 100
434 ms40824 KiB
// FUCKED UP FUCKED UP FUCKED UP FUCKED UP FUCKED UP
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O2")

#define F first
#define S second
#define pb push_back
#define SZ(x) (ll)(x.size())
#define all(x) x.begin(),x.end()
#define MP make_pair

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=1e5+10, maxm=1e6+10, lg=17, mod=1e9+7, inf=1e18;

#define git(x) (x&-x)

ll n,m,A[maxn],B[maxn],C[maxn],par[maxn][lg+1],ss[maxn][lg+1],st[maxn],ft[maxn],tt,h[maxn],bit[maxn],dp[maxn];
vector<ll> g[maxn],Q[maxn];
void add(ll i,ll x){for(;i<maxn;i+=git(i))bit[i]+=x;}
ll get(ll i){ll ret=0;for(;i;i-=git(i))ret+=bit[i];return ret;}
void pfs(ll v=1,ll p=0){
	st[v]=++tt;
	h[v]=h[par[v][0]=p]+1; for(int i=1;i<=lg;i++) par[v][i]=par[par[v][i-1]][i-1];
	for(auto u:g[v])if(u!=p) pfs(u,v);
	ft[v]=tt+1;
}
ll parx(ll v,ll x){
	if(x<=0) return v;
	for(int i=0;i<=lg;i++)if(x>>i&1) v=par[v][i];
	return v;
}
ll lca(ll v,ll u){
	if(h[v]<h[u]) swap(v,u);
	v=parx(v,h[v]-h[u]);
	if(v==u) return v;
	for(int i=lg;i>=0;i--)if(par[v][i]!=par[u][i]) v=par[v][i], u=par[u][i];
	return par[v][0];
}
void dfs(ll v=1,ll p=0){
	ll bac=0;
	for(auto u:g[v])if(u!=p) dfs(u,v), bac+=dp[u];
	dp[v]=bac;
	for(auto i:Q[v]) dp[v]=max(dp[v],C[i]+bac+get(st[A[i]])+get(st[B[i]]));
	//cout<<v<<' '<<dp[v]<<endl;
	add(st[v],bac-dp[v]);
	add(ft[v],-(bac-dp[v]));
}

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	cin>>n;
	for(int i=1;i<n;i++){
		ll v,u; cin>>v>>u;
		g[v].pb(u), g[u].pb(v);
	}
	pfs();
	cin>>m;
	for(int i=0;i<m;i++) cin>>A[i]>>B[i]>>C[i], Q[lca(A[i],B[i])].pb(i);
	dfs();
	cout<<dp[1];

	return 0;
}
// a denial a denial a denial a denial a denial a denial
#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...