题意：给你一颗有根树，它的孩子要么只有两个，要么没有，且每个点都有一个权值w。
接着给你一个权值为x的球，它从更节点开始向下掉，有三种情况
x=w[now]：停在此点
x<w[now]：当有孩子时：1/2可能性到左孩子，1/2可能性到右孩子
x>w[now]：当有孩子时：1/8可能性到左孩子，7/8可能性到右孩子
再给你一个点U，问你从根节点到U结点的可能性为多少 7^x/2^y ,求出x y
题解：非常经典的一个题，我使用邻接表存储，接着使用dfs遍历，最后树状数组维护结果。
我们可以知道 1/2：y++ 1/8：y+=3 7/8：x++，y+=3
接着就是每次只需要找到唯一一条从根到U点父节点的所有权值
接着找：左孩子中小于X的个数，右孩子中小于X的个数，左孩子中大于X的个数，右孩子中大于X的个数，但是我们要注意一个情况就是当有等于X的时候就不能到达U
这样我们可以离线vector存储问题（同一个点不同则存在一起），从根节点开始dfs遍历每个点
当走孩子节点时就把此点的权值加入数组（开两个数组），回溯时删除此权值
在添加前就此点权值寻找上诉四个值，并利用树状数组维护
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<string>
#include<cstdio>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1E-8
/*注意可能会有输出-0.000*/
#define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型
#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化
#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0
#define mul(a,b) (a<<b)
#define dir(a,b) (a>>b)
typedef long long ll;
typedef unsigned long long ull;
const int Inf=<<;
const double Pi=acos(-1.0);
const int Mod=1e9+;
const int Max=;//包括询问
int head[Max],nnext[Max],to[Max],chi[Max],e;//邻接表存树 dfs遍历
struct node
{
int val,poi;
} que[Max]; //问题
int dir[][]= {{,},{,},{,}}; //比x大的孩子 比x小的左孩子 比x小的右孩子
map<int,int> mp;//离散化
int val[Max];
vector<int> vec[Max];//存下这个点有哪些权值
int len[Max],ansx[Max],ansy[Max];
int nn;//总权值点
void Init(int n,int *lbit,int *rbit)
{
for(int i=; i<=n; ++i)
{
len[i]=;
ansx[i]=;
ansy[i]=;
head[i]=-;
vec[i].clear();
}
e=;
nn=;
mp.clear();
memset(lbit,,sizeof(lbit));
memset(rbit,,sizeof(rbit));
return;
}
void AddEdge(int u,int v,int ch)
{
nnext[e]=head[u];
to[e]=v;
chi[e]=ch;
head[u]=e++;
return;
}
int lowbit(int x)
{
return x&(-x);
}
void Add(int x,int y,int *bit)
{
while(x<=nn)
{
bit[x]+=y;
x+=lowbit(x);
}
return;
}
int Sum(int x,int *bit)
{
int sum=;
while(x)
{
sum+=bit[x];
x-=lowbit(x);
}
return sum;
}
int bit[][Max];//区分左右孩子
void dfs(int son,int tol1,int tol2)//遍历邻接表
{
int now=mp[val[son]];
for(int i=; i<len[son]; ++i)
{
int now1=mp[que[vec[son][i]].val];
int lef1=Sum(now1,bit[]);
int lef2=Sum(now1-,bit[]);
int rig1=Sum(now1,bit[]);
int rig2=Sum(now1-,bit[]);
if(lef1-lef2||rig1-rig2)
{
ansx[vec[son][i]]=-;
}
else//求值
{
ansx[vec[son][i]]=rig2*dir[][]; ansy[vec[son][i]]=(tol1-lef1)*dir[][];
ansy[vec[son][i]]+=(tol2-rig1)*dir[][];
ansy[vec[son][i]]+=lef2*dir[][];
ansy[vec[son][i]]+=rig2*dir[][];
}
}
for(int i=head[son]; ~i; i=nnext[i])
{
Add(now,,bit[chi[i]]);//加点
if(!chi[i])
dfs(to[i],tol1+,tol2);
else
dfs(to[i],tol1,tol2+);
Add(now,-,bit[chi[i]]);//删点
}
return;
}
int main()
{
int t,n,m,q;
int u,a,b;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
Init(n,bit[],bit[]);
for(int i=; i<=n; ++i)
{
scanf("%d",&val[i]);
mp[val[i]]=;
}
scanf("%d",&m);
for(int i=; i<m; ++i)//邻接表
{
scanf("%d %d %d",&u,&a,&b);
AddEdge(u,a,);
AddEdge(u,b,);
}
scanf("%d",&q);
for(int i=; i<q; ++i)
{
scanf("%d %d",&que[i].poi,&que[i].val);
vec[que[i].poi].push_back(i);//根据树上某点存que小标
len[que[i].poi]++;
mp[que[i].val]=;
}
int cnt=;
for(map<int,int>::iterator it=mp.begin(); it!=mp.end(); ++it) //离散化
{
it->second=cnt++;
nn++;
}
dfs(,,);
for(int i=; i<q; ++i)
{
if(ansx[i]==-)
printf("0\n");
else
printf("%d %d\n",ansx[i],ansy[i]);
}
}
return ;
}