Magic Ball Game
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 309 Accepted Submission(s): 73
Problem Description
When the magic ball game turns up, Kimi immediately falls in it. The interesting game is made up of N balls, each with a weight of w[i]. These N balls form a rooted tree, with the 1st ball as the root. Any ball in the game has either 0 or 2 children ball. If a node has 2 children balls, we may define one as the left child and the other as the right child.
The rules are simple: when Kimi decides to drop a magic ball with a weight of X, the ball goes down through the tree from the root. When the magic ball arrives at a node in the tree, there's a possibility to be catched and stop rolling, or continue to roll down left or right. The game ends when the ball stops, and the final score of the game depends on the node at which it stops.
After a long-time playing, Kimi now find out the key of the game. When the magic ball arrives at node u weighting w[u], it follows the laws below:
1 If X=w[u] or node u has no children balls, the magic ball stops.
2 If X<w[u], there's a possibility of 1/2 for the magic ball to roll down either left or right.
3 If X>w[u], the magic ball will roll down to its left child in a possibility of 1/8, while the possibility of rolling down right is 7/8.
In order to choose the right magic ball and achieve the goal, Kimi wonders what's the possibility for a magic ball with a weight of X to go past node v. No matter how the magic ball rolls down, it counts if node v exists on the path that the magic ball goes along.
Manual calculating is fun, but programmers have their ways to reach the answer. Now given the tree in the game and all Kimi's queries, you're required to answer the possibility he wonders.
Input
The input contains several test cases. An integer T(T≤15) will exist in the first line of input, indicating the number of test cases.
Each test case begins with an integer N(1≤N≤105), indicating the number of nodes in the tree. The following line contains N integers w[i], indicating the weight of each node in the tree. (1 ≤ i ≤ N, 1 ≤ w[i] ≤ 109, N is odd)
The following line contains the number of relationships M. The next M lines, each with three integers u,a and b(1≤u,a,b≤N), denotes that node a and b are respectively the left child and right child of node u. You may assume the tree contains exactly N nodes and (N-1) edges.
The next line gives the number of queries Q(1≤Q≤105). The following Q lines, each with two integers v and X(1≤v≤N,1≤X≤109), describe all the queries.
Output
If the magic ball is impossible to arrive at node v, output a single 0. Otherwise, you may easily find that the answer will be in the format of 7x/2y . You're only required to output the x and y for each query, separated by a blank. Each answer should be put down in one line.
思路: 首先考慮一個詢問（V,X），若從根節點到V節點的路徑上（不包括V）已存在權值為X的節點，則小球不可能到達V節點，否則，不妨定義往左走的路徑為“左路徑”，往右走的路徑稱為“右路徑”。設lmi，lma，rmi，rma分別表示左路徑上小於X的節點數，左路徑上大於X的節點數，右路徑上小於X的節點數，右路徑上大於X的節點數，則最終的答案即為： （1/2）^(lma+rma)*(7/8)^(rmi)*（1/8）^(lmi)。即輸出 rmi 和 3*（lmi+rmi）+（lma+rma）即可。
對於本題，我們可以離線處理每個節點上的詢問，從根節點做一次DFS，在過程中每經過一個節點就處理該節點所對應的詢問，我們可以用線段樹，樹狀數組等數據結構記錄從根節點到V的路徑上所有的權值（不包括V），然後就可以得到lmi，lma，rmi，rma，剩下的就是更行答案了，另外X很大，需要離散化處理。
代碼如下：
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <vector>
#define maxn 100010
#define mid ((t[p].l+t[p].r)>>1)
#define ls (p<<1)
#define rs (ls|1)
using namespace std;
struct Tree
{
int w;
int left,right;
}node[maxn];
vector<int> vec[maxn];
int c[maxn<<1][2];
void init(int n)
{
for(int i=0;i<=n;i++)
{
vec[i].clear();
node[i].left=node[i].right=node[i].w=-1;
}
}
void add(int a,int b,int c)
{
node[a].left=b;
node[a].right=c;
}
int ans[maxn][2],vis[maxn],po[maxn<<1],len;
int lowbit(int x)
{
return x&(-x);
}
void addnum(int x,int val,int tt)
{
while(x<=len)
{
c[x][tt]+=val;
x+=lowbit(x);
}
}
int getsum(int x,int tt)
{
int sum=0;
while(x>0)
{
sum+=c[x][tt];
x-=lowbit(x);
}
return sum;
}
int search(int len,int x)
{
int mi=1,ma=len,Mid;
while(mi<=ma)
{
Mid=(mi+ma)>>1;
if(po[Mid]==x)
return Mid;
if(po[Mid]<x)
mi=Mid+1;
else
ma=Mid-1;
}
}
void dfs(int now)
{
int i,w=search(len,node[now].w);
for(i=0;i<vec[now].size();i+=2)
{
int x=search(len,vec[now][i]),num=vec[now][i+1];
if(getsum(x,0)-getsum(x-1,0)>0||getsum(x,1)-getsum(x-1,1)>0)//如果已經存在x
{
ans[num][0]=-1;
}
else
{
int lma,lmi,rma,rmi;// 左邊大於，左邊小於，右邊大於，右邊小於
lmi=getsum(x-1,0);
lma=getsum(len,0)-getsum(x,0);
rmi=getsum(x-1,1);
rma=getsum(len,1)-getsum(x,1);
ans[num][0]=rmi;
ans[num][1]=3*(rmi+lmi)+rma+lma;
}
}
if(node[now].left!=-1)
{
addnum(w,1,0);
dfs(node[now].left);
addnum(w,-1,0);
}
if(node[now].right!=-1)
{
addnum(w,1,1);
dfs(node[now].right);
addnum(w,-1,1);
}
}
int main()
{
//freopen("dd.txt","r",stdin);
int ncase;
scanf("%d",&ncase);
while(ncase--)
{
int n,i,m,q,x,v;
scanf("%d",&n);
init(n);
for(i=1;i<=n;i++)
{
scanf("%d",&node[i].w);
po[i]=node[i].w;
}
scanf("%d",&m);
int a,b,cc;
memset(vis,0,sizeof(vis));
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&cc);
add(a,b,cc);
vis[b]=vis[cc]=1;
}
scanf("%d",&q);
for(i=1;i<=q;i++)
{
scanf("%d%d",&v,&x);
vec[v].push_back(x);
vec[v].push_back(i);
po[i+n]=x;
}
sort(po+1,po+q+n+1);
len=unique(po+1,po+q+n+1)-(po+1);
int root;
for(i=1;i<=n;i++)
{
if(!vis[i])
{
root=i;
break;
}
}
for(i=0;i<=len;i++)
c[i][0]=c[i][1]=0;
dfs(root);
for(i=1;i<=q;i++)
{
if(ans[i][0]==-1)
printf("0\n");
else
printf("%d %d\n",ans[i][0],ans[i][1]);
}
}
return 0;
}
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <vector>
#define maxn 100010
#define mid ((t[p].l+t[p].r)>>1)
#define ls (p<<1)
#define rs (ls|1)
using namespace std;
struct Tree
{
int w;
int left,right;
}node[maxn];
vector<int> vec[maxn];
int c[maxn<<1][2];
void init(int n)
{
for(int i=0;i<=n;i++)
{
vec[i].clear();
node[i].left=node[i].right=node[i].w=-1;
}
}
void add(int a,int b,int c)
{
node[a].left=b;
node[a].right=c;
}
int ans[maxn][2],vis[maxn],po[maxn<<1],len;
int lowbit(int x)
{
return x&(-x);
}
void addnum(int x,int val,int tt)
{
while(x<=len)
{
c[x][tt]+=val;
x+=lowbit(x);
}
}
int getsum(int x,int tt)
{
int sum=0;
while(x>0)
{
sum+=c[x][tt];
x-=lowbit(x);
}
return sum;
}
int search(int len,int x)
{
int mi=1,ma=len,Mid;
while(mi<=ma)
{
Mid=(mi+ma)>>1;
if(po[Mid]==x)
return Mid;
if(po[Mid]<x)
mi=Mid+1;
else
ma=Mid-1;
}
}
void dfs(int now)
{
int i,w=search(len,node[now].w);
for(i=0;i<vec[now].size();i+=2)
{
int x=search(len,vec[now][i]),num=vec[now][i+1];
if(getsum(x,0)-getsum(x-1,0)>0||getsum(x,1)-getsum(x-1,1)>0)//如果已經存在x
{
ans[num][0]=-1;
}
else
{
int lma,lmi,rma,rmi;// 左邊大於，左邊小於，右邊大於，右邊小於
lmi=getsum(x-1,0);
lma=getsum(len,0)-getsum(x,0);
rmi=getsum(x-1,1);
rma=getsum(len,1)-getsum(x,1);
ans[num][0]=rmi;
ans[num][1]=3*(rmi+lmi)+rma+lma;
}
}
if(node[now].left!=-1)
{
addnum(w,1,0);
dfs(node[now].left);
addnum(w,-1,0);
}
if(node[now].right!=-1)
{
addnum(w,1,1);
dfs(node[now].right);
addnum(w,-1,1);
}
}
int main()
{
//freopen("dd.txt","r",stdin);
int ncase;
scanf("%d",&ncase);
while(ncase--)
{
int n,i,m,q,x,v;
scanf("%d",&n);
init(n);
for(i=1;i<=n;i++)
{
scanf("%d",&node[i].w);
po[i]=node[i].w;
}
scanf("%d",&m);
int a,b,cc;
memset(vis,0,sizeof(vis));
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&cc);
add(a,b,cc);
vis[b]=vis[cc]=1;
}
scanf("%d",&q);
for(i=1;i<=q;i++)
{
scanf("%d%d",&v,&x);
vec[v].push_back(x);
vec[v].push_back(i);
po[i+n]=x;
}
sort(po+1,po+q+n+1);
len=unique(po+1,po+q+n+1)-(po+1);
int root;
for(i=1;i<=n;i++)
{
if(!vis[i])
{
root=i;
break;
}
}
for(i=0;i<=len;i++)
c[i][0]=c[i][1]=0;
dfs(root);
for(i=1;i<=q;i++)
{
if(ans[i][0]==-1)
printf("0\n");
else
printf("%d %d\n",ans[i][0],ans[i][1]);
}
}
return 0;
}
