题目大意很简单。
有一颗树(10^5结点)，所有结点要么没有子结点，要么有两个子结点。然后每个结点都有一个重量值，根结点是1
然后有一个球，从结点1开始往子孙结点走。
每碰到一个结点，有三种情况
如果此球重量等于该结点重量，球就停下了
如果此球重量小于该结点重量，则分别往左右儿子走的可能都是1/2
如果此球重量大于该结点重量，则走向左儿子的概率是1/8，右儿子的概率是7/8
然后若干个询问（10^5次），问一个重量为x的球经过结点v的概率
仔细想一下，一个球走到某个结点，路径已经是固定的了，但是暴力肯定会超时，那么观察路径，可以发现路径可以分成两种，向左走的路径和向右走的路
径，分成这两种的原因也是因为各自的计算公式，在向左走的路径中，设大于x的点权有a个，小于x的点权有b个，那么向左走的路径概率就是p1=
(1/2)^a * (1/8) ^b， 同理向右的路径中概率
p2 = (1/2)^c * (7/8) ^d，最后二者相乘即是答案。
p1*p2则分母的指数就是d，分子的指数即为d/(a+c+3*b+3*d)
需要注意的是，如果从1到该点的路径中有一个点的重量等于x，那么这个点是永远被达不到的。
用树状数组维护指数即可
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
const int MAXN=;
int next[MAXN][];
int n;
int root;
int w[MAXN];
struct QQ
{
int v;
int X;
int ans1,ans2;
}Query[MAXN];
vector<int>vec[MAXN];
bool used[MAXN];
int a[MAXN];
map<int,int>mp; int c1[MAXN];
int c2[MAXN];
int t;
int lowbit(int x)
{
return x&(-x);
}
void add1(int i,int val)
{
while(i <= t)
{
c1[i] += val;
i += lowbit(i);
}
}
int sum1(int i)
{
int s = ;
while(i > )
{
s += c1[i];
i -= lowbit(i);
}
return s;
}
void add2(int i,int val)
{
while(i <= t)
{
c2[i] += val;
i += lowbit(i);
}
}
int sum2(int i)
{
int s = ;
while(i > )
{
s += c2[i];
i -= lowbit(i);
}
return s;
} void dfs(int u)
{
int sz = vec[u].size();
for(int i = ;i < sz;i++) //对于每个点上的询问
{
int id = vec[u][i];
int X = mp[Query[id].X];
if(sum1(X)-sum1(X-)!= || sum2(X)-sum2(X-)!=)
{
Query[id].ans1 = Query[id].ans2 = -;
}
else
{
Query[id].ans1 = Query[id].ans2 = ;
Query[id].ans2 += *sum1(X-)+sum1(t)-sum1(X);
Query[id].ans1 += sum2(X-);
Query[id].ans2 += *sum2(X-)+sum2(t)-sum2(X);
}
}
if(next[u][]== && next[u][]==)return;
add1(mp[w[u]],); //保证是有序的
dfs(next[u][]); //左走
add1(mp[w[u]],-); //恢复
add2(mp[w[u]],); //右走
dfs(next[u][]);
add2(mp[w[u]],-); //回溯法
} int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int T;
int m;
int u,x,y;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i = ;i <= n;i++)
{
used[i] = false;
next[i][] = next[i][] = ;
vec[i].clear();
}
t = ;
for(int i = ;i <= n;i++)
{
scanf("%d",&w[i]);
a[t++] = w[i];
}
scanf("%d",&m);
while(m--)
{
scanf("%d%d%d",&u,&x,&y);
used[x] = true;
used[y] = true;
next[u][] = x;
next[u][] = y;
}
scanf("%d",&m);
for(int i = ;i < m;i++)
{
scanf("%d%d",&u,&x);
Query[i].v = u;
Query[i].X = x;
a[t++] = x;
vec[u].push_back(i);
}
for(int i = ;i <= n;i++)
if(!used[i])
{
root = i;
break;
}
sort(a,a+t);
t = unique(a,a+t)-a;
mp.clear();
for(int i = ;i < t;i++)
mp[a[i]]=i+;
memset(c1,,sizeof(c1));
memset(c2,,sizeof(c2));
dfs(root);
for(int i = ;i < m;i++)
{
if(Query[i].ans1 == -)
printf("0\n");
else printf("%d %d\n",Query[i].ans1,Query[i].ans2);
}
}
return ;
}