Submission #734247

#	Time	Username	Problem	Language	Result	Execution time	Memory
734247		PoPularPlusPlus	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	208 ms	34756 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007; 
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

bool remender(ll a , ll b){return a%b;}

//freopen("problemname.in", "r", stdin);
//freopen("problemname.out", "w", stdout);

struct Fen {
	
	vector<int> tree;
	
	void init(int n){
		tree.assign(n + 1 , 0LL);
	}
	
	void set(int i , int val , int n){
		i++;
		while(i <= n){
			tree[i] += val;
			i += (i & (-i));
		}
	}
	
	int sum(int i){
		i++;
		ll ans = 0;
		while(i > 0){
			ans += tree[i];
			i -= (i & (-i));
		}
		return ans;
	}
	
	void build(vector<int>& a){
		int n = a.size();
		for(int i = 0; i < n; i++){
			set(i , a[i] , n);
		}
	}
	
};

struct item {
	int a ,  b ,  lca ,  c;
};

item make(int a , int b , int lca, int c){
	item it;
	it.a = a;
	it.b = b;
	it.lca = lca;
	it.c = c;
	return it;
}

const int N = 100002,L=20;

int timer , tin[N],tout[N],up[N][L],ft[2*N];
vector<int> adj[N],pos[N];
vector<item> v;
int dp[N],sum[N],n;
Fen ft_dp,ft_sum;

void bl(int node , int par){
	up[node][0] = par;
	ft[timer] = node;
	tin[node] = timer++;
	for(int i = 1; i < L; i++){
		up[node][i] = up[up[node][i-1]][i-1];
	}
	for(int i : adj[node]){
		if(i!=par){
			bl(i , node);
		}
	}
	ft[timer] = node;
	tout[node] = timer++;
}

bool is_lca(int x , int y){
	return tin[x] <= tin[y] && tout[x] >= tout[y];
}

int find(int x , int y){
	if(is_lca(x,y))return x;
	if(is_lca(y,x))return y;
	for(int i = L - 1; i >= 0; i--){
		if(!is_lca(up[x][i] , y))x = up[x][i];
	}
	return up[x][0];
}

void dfs(int node , int par){
	sum[node] = 0;
	for(int i : adj[node]){
		if(i!=par){
			dfs(i,node);
			sum[node] += dp[i];
		}
	}
	dp[node] = sum[node];
	for(int i : pos[node]){
		int res = 0;
		if(v[i].a != node){
			res += ft_sum.sum(tin[v[i].a]) - ft_sum.sum(tin[node]);
			res -= ft_dp.sum(tin[v[i].a]) - ft_dp.sum(tin[node]);
		}
		if(v[i].b != node){
			res += ft_sum.sum(tin[v[i].b]) - ft_sum.sum(tin[node]);
			res -= ft_dp.sum(tin[v[i].b]) - ft_dp.sum(tin[node]);
		}
		res += sum[node];
		res += v[i].c;
		dp[node] = max(dp[node] , res);
	}
	ft_sum.set(tin[node],sum[node],2*n);
	ft_sum.set(tout[node],-sum[node],2*n);
	ft_dp.set(tin[node],dp[node],2*n);
	ft_dp.set(tout[node],-dp[node],2*n);
}

void solve(){
	cin >> n;
	for(int i = 0; i < n - 1; i++){
		int a , b;
		cin >> a >> b;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	timer = 0;
	bl(1,1);
	int m;
	cin >> m;
	for(int i = 0; i < m; i++){
		int a , b , c;
		cin >> a >> b >> c;
		int lca = find(a,b);
		v.pb(make(a,b,lca,c));
		pos[lca].pb(i);
	}
	ft_dp.init(2*n);
	ft_sum.init(2*n);
	dfs(1,1);
	cout << dp[1] << '\n';
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
	//int t;cin >> t;while(t--)
	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