题意:根为1的N≤105个节点的无向树,所有结点有2个儿子或者没有儿子
每个节点的重量wi≤109,然后有一个球,从根开始往儿子结点走
每碰到一个节点，有三种情况:
如果此球重量等于该节点重量或者没有儿子节点了，球就停下了
如果此球重量小于该节点重量，则分别往左右儿子走的可能都是1/2
如果此球重量大于该节点重量，则走向左儿子的概率是1/8，右儿子的概率是7/8
Q≤105询问,问一个重量为x的球经过节点v的概率,表示成7x/2y,输出x,y
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
int n, m, q;
int son[N][2], w[N];
vector<pair<int, int> > Q[N];struct BIT {int n, b[N << 1];void init(int _n) {n = _n;memset(b, 0, sizeof b);}void add(int i, int v) {for(; i <= n; i += i & -i)b[i] += v;}int sum(int i) {int ret = 0;for(; i; i -= i & -i) ret += b[i];return ret;}int getAll() {return sum(n);}
} bit[2]; //0 for left, 1 for rightvector<int> xs;
pair<int, int> ans[N];//ans = 1/2 ^ leftLarge * 1/8 ^ leftSmall;
// * 1/2 ^ rightLarge * 7/8 ^ rightSmall;void dfs(int u) {int leftAll = bit[0].getAll(), rightAll = bit[1].getAll();for(auto p : Q[u]) { //answer queriesint x = p.first, id = p.second;x = lower_bound(xs.begin(), xs.end(), x) - xs.begin() + 1;int leftSmall = bit[0].sum(x - 1), leftLarge = leftAll - bit[0].sum(x);int rightSmall = bit[1].sum(x - 1), rightLarge = rightAll - bit[1].sum(x);//if equal ones existif(leftAll + rightAll - leftSmall - leftLarge - rightSmall - rightLarge) {ans[id] = { -1, -1};continue;}ans[id].first = rightSmall;ans[id].second = leftLarge + rightLarge + 3 * (leftSmall + rightSmall);}w[u] = lower_bound(xs.begin(), xs.end(), w[u]) - xs.begin() + 1;for(int i = 0; i < 2; ++i) {int v = son[u][i];if(!v) continue;bit[i].add(w[u], 1); //add before go downdfs(v);bit[i].add(w[u], -1); //back}
}int main() {int t; scanf("%d", &t);while(t--) {scanf("%d", &n);xs.clear();for(int i = 1; i <= n; ++i) {scanf("%d", w + i);xs.push_back(w[i]);}scanf("%d", &m);memset(son, 0, sizeof son);while(m--) {int u; scanf("%d", &u);for(int i = 0; i < 2; ++i)scanf("%d", son[u] + i);}scanf("%d", &q);for(int i = 1; i <= n; ++i) Q[i].clear();for(int i = 1; i <= q; ++i) {int v, x; scanf("%d%d", &v, &x);xs.push_back(x);Q[v].push_back({x, i});}sort(xs.begin(), xs.end());xs.resize(unique(xs.begin(), xs.end()) - xs.begin());for(int i = 0; i < 2; ++i) bit[i].init(xs.size());dfs(1);for(int i = 1; i <= q; ++i)if(~ans[i].first) printf("%d %d\n", ans[i].first, ans[i].second);else puts("0");}return 0;
}