/* Note that MCMF routine is taken from http://shygypsy.com/tools/mcmf4.cpp. */ #include <bits/stdc++.h> using namespace std; // the maximum number of vertices + 1 #define NN 410 // adjacency matrix (fill this up) int cap[NN][NN]; // cost per unit of flow matrix (fill this up) int cost[NN][NN]; // flow network and adjacency list int fnet[NN][NN], adj[NN][NN], deg[NN]; // Dijkstra's predecessor, depth and priority queue int par[NN], d[NN], q[NN], inq[NN], qs; // Labelling function int pi[NN]; #define CLR(a, x) memset( a, x, sizeof( a ) ) #define Inf (INT_MAX/2) #define BUBL { \ t = q[i]; q[i] = q[j]; q[j] = t; \ t = inq[q[i]]; inq[q[i]] = inq[q[j]]; inq[q[j]] = t; } // Dijkstra's using non-negative edge weights (cost + potential) #define Pot(u,v) (d[u] + pi[u] - pi[v]) bool dijkstra( int n, int s, int t ) { CLR( d, 0x3F ); CLR( par, -1 ); CLR( inq, -1 ); //for( int i = 0; i < n; i++ ) d[i] = Inf, par[i] = -1; d[s] = qs = 0; inq[q[qs++] = s] = 0; par[s] = n; while( qs ) { // get the minimum from q and bubble down int u = q[0]; inq[u] = -1; q[0] = q[--qs]; if( qs ) inq[q[0]] = 0; for( int i = 0, j = 2*i + 1, t; j < qs; i = j, j = 2*i + 1 ) { if( j + 1 < qs && d[q[j + 1]] < d[q[j]] ) j++; if( d[q[j]] >= d[q[i]] ) break; BUBL; } // relax edge (u,i) or (i,u) for all i; for( int k = 0, v = adj[u][k]; k < deg[u]; v = adj[u][++k] ) { // try undoing edge v->u if( fnet[v][u] && d[v] > Pot(u,v) - cost[v][u] ) d[v] = Pot(u,v) - cost[v][par[v] = u]; // try using edge u->v if( fnet[u][v] < cap[u][v] && d[v] > Pot(u,v) + cost[u][v] ) d[v] = Pot(u,v) + cost[par[v] = u][v]; if( par[v] == u ) { // bubble up or decrease key if( inq[v] < 0 ) { inq[q[qs] = v] = qs; qs++; } for( int i = inq[v], j = ( i - 1 )/2, t; d[q[i]] < d[q[j]]; i = j, j = ( i - 1 )/2 ) BUBL; } } } for( int i = 0; i < n; i++ ) if( pi[i] < Inf ) pi[i] += d[i]; return par[t] >= 0; } #undef Pot int mcmf4( int n, int s, int t, int &fcost ) { // build the adjacency list CLR( deg, 0 ); for( int i = 0; i < n; i++ ) for( int j = 0; j < n; j++ ) if( cap[i][j] || cap[j][i] ) adj[i][deg[i]++] = j; CLR( fnet, 0 ); CLR( pi, 0 ); int flow = fcost = 0; // repeatedly, find a cheapest path from s to t while( dijkstra( n, s, t ) ) { // get the bottleneck capacity int bot = INT_MAX; for( int v = t, u = par[v]; v != s; u = par[v = u] ) { int t = fnet[v][u] ? fnet[v][u] : ( cap[u][v] - fnet[u][v] ); if (t < bot) bot = t; } // update the flow network for( int v = t, u = par[v]; v != s; u = par[v = u] ) if( fnet[v][u] ) { fnet[v][u] -= bot; fcost -= bot * cost[v][u]; } else { fnet[u][v] += bot; fcost += bot * cost[u][v]; } flow += bot; } return flow; } void AddEdge(int from, int to, int _cap, int _cost) { cap[from][to] = _cap; cost[from][to] = _cost; } int n; vector<vector<int> > g(100005); int child[100005]; int value[100005]; void dfs(int from, int par = -1) { int cnt = 0; for (int i = 0; i < g[from].size(); i++) { int to = g[from][i]; if (to != par) { dfs(to, from); cnt ++; } } child[from] = cnt; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> n; for (int i = 0; i < n; i++) cin >> value[i]; for (int i = 0; i + 1 < n; i++) { int from, to; cin >> from >> to; from --, to --; g[from].push_back(to); g[to].push_back(from); } dfs(0); int query; cin >> query; while (query --) { memset(cap, 0, sizeof(cap)); int m, x, y; cin >> m >> x >> y; vector<int> v (m); for (int i = 0; i < m; i++) { cin >> v[i]; } // 1 + m vector<pair<int, int> > lessX, greatX; for (int i = 0; i < n; i++) { if (child[i] < x) lessX.push_back(make_pair(value[i], child[i])); else greatX.push_back(make_pair(value[i], child[i])); } int sz1 = min((int) lessX.size(), m); int sz2 = min((int) greatX.size(), 1); sort(lessX.begin(), lessX.end()); sort(greatX.begin(), greatX.end()); // total 1 + m + m + m + sz1 + sz2 + 1 int total = 1 + m + m + m + sz1 + sz2 + 1; int source = 0, sink = total - 1; for (int i = 0; i < m; i++) { AddEdge(source, i + 1, 1, 0); } // necessary to insert to take care of the order of query. for (int i = 0; i < m; i++) for (int j = 0; j < i; j++) { AddEdge(1 + i, 1 + m + j, 1, v[i] * v[j]); AddEdge(1 + i, 1 + m + m + j, 1, v[i] * v[j]); } for (int i = 0; i < m; i++) for (int j = 0; j < sz1; j++) { AddEdge(1 + i, 1 + m + m + m + j, 1, v[i] * lessX[j].first); } for (int i = 0; i < m; i++) for (int j = 0; j < sz2; j++) { AddEdge(1 + i, 1 + m + m + m + sz1 + j, 1, v[i] * greatX[j].first); } // add edges to sink node. // type 1 for (int i = 0; i < m; i++) { AddEdge(1 + m + i, sink, x, 0); } // type 2 for (int i = 0; i < m; i++) { AddEdge(1 + m + m + i, sink, m, y); } // type 3 for (int i = 0; i < sz1; i++) { AddEdge(1 + m + m + m + i, sink, x - lessX[i].second, 0); } // type 4 for (int i = 0; i < sz2; i++) { AddEdge(1 + m + m + m + sz1 + i, sink, m, y); } int fcost = 0; int flow = mcmf4(total, source, sink, fcost); assert(flow == m); cout << fcost << endl; } return 0; }