【题意】
多校的一个题目。
根为1的N<=100000个节点的无向树,所有节点有两个儿子或者没有儿子。每个节点的重量wi<=1e9,然后现在有一个球从根节点向儿子节点走。
每碰到一个球,有3种情况:
1:如果此球重量等于该节点重量或者没有儿子节点了,球就停下了
2:如果此球重量小于该节点重量,则分别往左右儿子走的可能都是1/2
3:如果此球重量大于该节点重量,则走向左儿子的概率是1/8,右儿子的概率是7/8
Q≤105询问,问一个重量为x的球经过节点v的概率,表示成7x/2y,输出x,y
【解题方法】
离线BIT的做法比较显然,但是这题代码真的好难写,而且对着别人的代码,调了好久好久才过题。
首先树上2点之间的路径是唯一的,所以离线询问按照dfs序来回答询问
离散化之后用2颗BIT来记录左路径和右路径上经过的点的重量
ans=1/2leftLarge∗1/8leftSmall∗1/2rightLarge∗7/8rightSmall
即x=rightSmall,y=leftLarge+rightLarge+3∗(leftSmall+rightSmall)
递归之前添加,别忘记回溯就好
时间复杂度为O((n+q)logn)
【AC代码】
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=1e5+10;
inline int read() //读入挂
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,m,q,u,v,x;
int son[maxn][2],w[maxn];//存储数据
vector<pair<int,int> >Q[maxn];//询问
vector<int>xs;//离散化
pair<int,int>ans[maxn]; //存储答案
int lowbit(int x){
return (x&(-x));
}
struct BIT{
int n;int c[maxn*2];
void init(int _n){
n=_n;
memset(c,0,sizeof(c));
}
void add(int i,int v){
while(i<=n){
c[i]+=v;
i+=lowbit(i);
}
}
int query(int i){
int ret=0;
while(i>0){
ret+=c[i];
i-=lowbit(i);
}
return ret;
}
int getall(){
return query(n);
}
}bit[2];
//void dfs(int u){
// int leftAll=bit[0].getall();
// int rightAll=bit[1].getall();
// for(auto p : Q[u]){
// int x=p.first;
// int id=p.second;
// x=lower_bound(xs.begin(),xs.end(),x)-xs.begin()+1;
// int leftSmall=bit[0].query(x-1),leftLarge=leftAll-bit[0].query(x);
// int rightSmall=bit[1].query(x-1),rightLarge=rightAll-bit[1].query(x);
// //判断存在相等
// if(leftAll+rightAll-leftLarge-leftSmall-rightLarge-rightSmall){
// 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);//递归之前添加
// dfs(v);
// bit[i].add(w[u],-1);//回溯
// }
//}
void dfs(int u) {
int leftAll = bit[0].getall(), rightAll = bit[1].getall();
for(auto p : Q[u]) { //answer queries
int x = p.first, id = p.second;
x = lower_bound(xs.begin(), xs.end(), x) - xs.begin() + 1;
int leftSmall = bit[0].query(x - 1), leftLarge = leftAll - bit[0].query(x);
int rightSmall = bit[1].query(x - 1), rightLarge = rightAll - bit[1].query(x);
//if equal ones exist
if(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 down
dfs(v);
bit[i].add(w[u], -1); //back
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--){
xs.clear();
scanf("%d",&n);
for(int i=1; i<=n; i++){
scanf("%d",&w[i]);
xs.push_back(w[i]);
}
scanf("%d",&m);
memset(son,0,sizeof(son));
for(int i=1; i<=m; i++){
scanf("%d",&u);
for(int j=0; j<2; j++){
scanf("%d",&son[u][j]);
}
}
scanf("%d",&q);
for(int i=1; i<=n; i++){
Q[i].clear();
}
for(int i=1; i<=q; i++){
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());
// cout<<xs.size()<<endl;
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");
}
}
}
}