CIRCUITS.cpp

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

const int MAXN = 100;
const double EPS = 1e-10;

//type: 0 - input, 1 - or, 2 - and
int prev[MAXN][2], type[MAXN];
double prob[MAXN];

double eval(int n, double p) {
   // cout<<"Hello"<<n<<"P"<<p;
  for (int i = 0; i < n; ++i) {
    if (type[i] == 0) prob[i] = p;
    else if (type[i] == 1) prob[i] = 1-(1-prob[prev[i][0]])*(1-prob[prev[i][1]]);
    else prob[i] = prob[prev[i][0]]*prob[prev[i][1]];
  }
  return prob[n-1];
}

double solve(int n) {
  double lo = 0, hi = 1;
  while (lo+EPS < hi) {
    double mid = (lo+hi)*0.5;
    if (eval(n,mid) < 0.5) lo = mid;
    else hi = mid;
  }
  return lo;
}

int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; ++i) {
      scanf("%d", &type[i]);
      if (type[i]) {
	scanf("%d%d", &prev[i][0], &prev[i][1]);
	--prev[i][0]; --prev[i][1];
      }
    }

    printf("%.5lf\n", double(solve(n)));
  }
}