题目描述：给你一个由 \(n\) 个电阻通过串并联构成的纯电阻电路，要求你给每个电阻分配一个阻值，使得每个电阻的阻值都是非负整数，整个电路的阻值为 \(r\)，所有电阻的阻值之和最小。求构造方案。共 \(t\) 组数据。

数据范围：\(t\le 32000,r\le 10^6,n\le 80000,\sum n\le 320000\)。

首先需要猜到一个结论，设 \(f_G(r)\) 是对于一个电路 \(G\) 的答案，则 \(f_G(r)=k_Gr\)，其中 \(k_G\) 是一个只与 \(G\) 有关的常数。因为 \(f_G(r)\propto r\) 是显然的。于是我们考虑如何求出 \(k_G\)。

设 \(G\) 的 \(m\) 个子电路为 \(G_i\)。

1. 串联，则 \(k_G=\min k_{G_i}\)。

2. 并联，\(\frac{1}{r}=\sum_{i=1}^m\frac{1}{r_i}\)，所以 \(f_G(r)=r(\sum_{i=1}^m\frac{1}{r_i})(\sum_{i=1}^mk_{G_i}r_i)\ge r(\sum_{i=1}^m\sqrt{\frac{1}{r_i}}\cdot\sqrt{k_{G_i}r_i})^2=r(\sum_{i=1}^m\sqrt{k_{G_i}})^2\)，所以 \(\sqrt{k_G}=\sum_{i=1}^m\sqrt{k_{G_i}}\)。此时取到等号的冲药条件就是 \(\frac{1}{r_i}\propto \sqrt{k_{G_i}}\)。

于是显然可以得出 \(\sqrt{k_G}\in \N\)。

因为串联只有一个电阻分到压，所以可以假设是有 \(\sqrt{k_G}\) 个电阻并联，每个电阻的阻值为 \(r\sqrt{k_G}\)。

#include<bits/stdc++.h>
#define Rint register int
#define MP make_pair
#define PB push_back
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
const int N = 1000003, mod = 998244353;
inline int ksm(int a, int b){
	int res = 1;
	for(;b;b >>= 1, a = (LL) a * a % mod) if(b & 1) res = (LL) res * a % mod;
	return res;
}
template<typename T>
inline void read(T &x){
	int ch = getchar(); x = 0; bool f = false;
	for(;ch < '0' || ch > '9';ch = getchar()) f |= ch == '-';
	for(;ch >= '0' && ch <= '9';ch = getchar()) x = x * 10 + ch - '0';
	if(f) x = -x;
}
template<typename T>
inline bool chmax(T &a, const T &b){if(a < b) return a = b, 1; return 0;}
template<typename T>
inline bool chmin(T &a, const T &b){if(a > b) return a = b, 1; return 0;}
int t, tot, op[N], cnt;
vector<int> G[N];
LL r, f[N];
int get(){int ch = getchar(); while(ch == ' ') ch = getchar(); return ch;}
int input(){
	int u = ++ tot;
	if(get() == '*'){f[u] = 1; op[u] = -1; return u;}
	G[u].PB(input()); int ch = get(); op[u] = ch == 'S'; G[u].PB(input());
	while(get() == ch) G[u].PB(input());
	if(op[u]){
		f[u] = 1e18; for(Rint v : G[u]) chmin(f[u], f[v]);
	} else {
		f[u] = 0; for(Rint v : G[u]) f[u] += f[v];
	} return u;
}
void dfs(int x, LL val){
	if(op[x] == -1){printf(" %I64d", val); if(val) ++ cnt; return;}
	if(op[x]){
		bool flag = true;
		for(Rint v : G[x])
			if(flag && f[x] == f[v]){flag = false; dfs(v, val);}
			else dfs(v, 0);
		return;
	}
	for(Rint v : G[x]) dfs(v, val);
}
void solve(){
	for(Rint i = 1;i <= tot;++ i){G[i].clear(); f[i] = op[i] = 0;} tot = cnt = 0;
	read(r); input(); dfs(1, r * f[1]);
}
int main(){
	read(t);
	while(t --){printf("REVOLTING"); solve(); putchar('\n');}
}