Submission #1359757

#TimeUsernameProblemLanguageResultExecution timeMemory
1359757axtelnRoadside Advertisements (NOI17_roadsideadverts)C++20
100 / 100
32 ms16796 KiB
#include <bits/stdc++.h>
#define qweqwe cin.tie(0)->sync_with_stdio(0)
using namespace std;
using ll = long long;
using pii = pair<ll,ll>;
using db = long double;

int t,sz;
vector<ll> tin,tout,dp;
vector<vector<ll>> lift;
vector<vector<pii>> graph;

void dfs(int x,int p,ll cur){
	tin[x]=++t;
	lift[x][0]=p;
	dp[x]=cur;
	for (int i=1;i<=sz;i++){
		lift[x][i]=lift[lift[x][i-1]][i-1];
	}
	for (pii i:graph[x]){	
		if (i.first==p) continue;
		dfs(i.first,x,cur+i.second);
	}tout[x]=++t;
}

bool mambo(int u,int v){
	return tin[u]<=tin[v]&&tout[u]>=tout[v];
}

ll lca(int u,int v){
	if (mambo(u,v)){
		return u;
	}
	if (mambo(v,u)){
		return v;
	}
	for (int i=sz;i>=0;i--){
		if (!mambo(lift[u][i],v)){
			u=lift[u][i];
		}
	}return lift[u][0];
}

int main(){
	qweqwe;
	int n;cin >> n;
	sz=ceil(log2(n));
	tin.resize(n);tout.resize(n);
	dp.resize(n);
	graph.resize(n);
	lift.assign(n,vector<ll>(sz+1));
	
	for (int i=0;i<n-1;i++){
		int a,b,c;cin >> a >> b >> c;
		graph[a].push_back({b,c});
		graph[b].push_back({a,c});
	}
	dfs(0,0,0);
	/*
	for (int i=0;i<n;i++){
		cout << dp[i] << " ";
	}cout << '\n';
	*/
	int q;cin >> q;
	for (int i=0;i<q;i++){
		vector<pii> arr;
		for (int i=0;i<5;i++){
			int a;cin >> a;
			arr.push_back({tin[a],a});
		}sort(arr.begin(),arr.end());
		ll sum=0;
		for (int i=0;i<4;i++){
			int u=arr[i].second,v=arr[i+1].second;
			ll d1=dp[u],d2=dp[v];
			ll to=d1+d2-2*dp[lca(u,v)];
			//cout << u << " " << v << " " << lca(u,v) << " -> " << to << "\n";
			sum+=to;
		}int u=arr[4].second,v=arr[0].second;
		ll d1=dp[u],d2=dp[v];
		ll to=d1+d2-2*dp[lca(u,v)];
		sum+=to;
		sum/=2;
		cout << sum << "\n";
	}
	return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...