Moving to Nuremberg Solution

nuremberg.cpp

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define F first
#define S second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

vector<pii> el;
vector<ll> ews;
vector<ll> freqs;

struct ART {
	ll ans = 0;
	ll weight = 0;
	ART operator+(const ART& otr) const {
		return {ans + otr.ans, weight + otr.weight};
	}
	ART promote(int x, int e) const { // x=node index, e=edge index
		return {ans + (weight + freqs[x]) * ews[e], weight + freqs[x]};
	}
};
template<class T>
struct AllRoots {
	int n;
	vector<vector<pii>> adj;
	vector<vector<T>> pre, suf;
	AllRoots(vector<pii>& el) : n(sz(el)+1), adj(sz(el)+1), pre(sz(el)+1), suf(sz(el)+1) {
		rep(i,0,n-1){
			adj[el[i].F].pb({el[i].S,i});
			adj[el[i].S].pb({el[i].F,i});
		}
		rep(i,0,n) {
			pre[i].resize(adj[i].size() + 1);
			suf[i].resize(adj[i].size() + 1);
		}
	}
	T get(int x, int i = 0){
		T& v = suf[x][i+1];
		if(i) v = pre[x][i] + v; 
		return v.promote(x, adj[x][i].S);
	};
	T down(int x, int p = -1) {
		for(auto& c : adj[x]) if(c.F == p) swap(c, adj[x][0]);
		for(int i = adj[x].size()-1; i > -(p<0); --i)
			suf[x][i] = down(adj[x][i].F, x) + suf[x][i+1];
		return get(x);
	}
	void up(int x, int p = -1) {
		rep(i, p != -1, adj[x].size()) {
			pre[x][i+1] = pre[x][i] + get(adj[x][i].F);
			pre[adj[x][i].F][1] = get(x, i);
			up(adj[x][i].F, x);
		}
	}
	static vector<T> calc(vector<pii>& el) {
		AllRoots ar(el);
		ar.down(0);
		ar.up(0);
		vector<T> res(ar.n);
		rep(i,0,ar.n) res[i] = ar.pre[i].back(); // optional promote here.
		return res;
	}
};

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
	int tests;cin>>tests;
	while(tests--){
		int n;cin>>n;
		ews.resize(n);
		el.resize(n-1);
		freqs.assign(n,0);
		rep(i,0,n-1){
			cin>>el[i].F>>el[i].S>>ews[i];
			el[i].F--; el[i].S--;
		}
		int m;cin>>m;
		rep(_,0,m){
			int x,f;cin>>x>>f;
			freqs[x-1]=f;
		}
		if(n==1){
			cout<<"0\n1\n";
			continue;
		}
		auto res = AllRoots<ART>::calc(el);
		ll best = 1e18;
		vi bests;
		rep(i,0,n) {
			if(res[i].ans == best) bests.pb(i+1);
			else if(res[i].ans < best) {
				best=res[i].ans;
				bests={i+1};
			}
		}
		cout<<2*best<<'\n';
		for(int v : bests)cout<<v<<' ';
		cout<<'\n';
	}
}