首页 > ACM题库 > HDU-杭电 > HDU 4605-Magic Ball Game-线段树-[解题报告]HOJ
2015
09-17

HDU 4605-Magic Ball Game-线段树-[解题报告]HOJ

Magic Ball Game

问题描述 :

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.

输入:

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.

输出:

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.

样例输入:

1
3
2 3 1
1
1 2 3
3
3 2
1 1
3 4

样例输出:

0
0 0
1 3

题目大意很简单。

有一颗树(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,最后二者相乘即是答案。

需要注意的是,如果从1到该点的路径中有一个点的重量等于x,那么这个点是永远被达不到的。

最后就是实现了。

看到要求大于某数的值有多少,一般就可以想到使用数据结构,如树状数组,线段树来统计。 而树状数组又是最好写的。

所以对于左右路径,分别开一个树状数组,用来维护大于某数的点有几个。

然后询问需要先存下来。在我们DFS遍历树的时候再处理。

然后维护树状数组的时候,用的是回溯的一种方法,保证遍历到某个点时,所用到的树状数组一定是只记录了1到该点的路径上的所有重量值

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <vector>
#define MAXM 111111
#define MAXN 111111
#define INF 1000000007
#define eps 1e-8
using namespace std;
vector<int>g[MAXN];
vector<pair<int, int> >query[MAXN];
int ta[2][MAXN];
int n, m, q, cnt;
int w[MAXN];
int a[MAXN * 2];
int ans[MAXN][2];
int lowbit(int x)
{
    return x & -x;
}
void add(int x, int v, int j)
{
    for(int i = x; i <= cnt; i += lowbit(i))
        ta[j][i] += v;
}
int getsum(int x, int j)
{
    int sum = 0;
    for(int i = x; i > 0; i -= lowbit(i))
        sum += ta[j][i];
    return sum;
}
void dfs(int u)
{
    int sz = query[u].size();
    for(int i = 0; i < sz; i++)
    {

        int weight = query[u][i].second;
        int id = query[u][i].first;
        int pos = lower_bound(a, a + cnt, weight) - a + 1;
        int ls = getsum(pos - 1, 0);
        int rs = getsum(pos - 1, 1);
        int lall = getsum(cnt, 0);
        int rall = getsum(cnt, 1);
        int lb = lall - getsum(pos, 0);
        int rb = rall - getsum(pos, 1);
        if(ls + lb + rs + rb - lall - rall != 0)
        {
            ans[id][0] = -1;
            continue;
        }
        ans[id][0] = ls * 3 + rs * 3 + lb + rb;
        ans[id][1] = rs;
    }
    sz = g[u].size();
    for(int i = 0; i < sz; i++)
    {
        int v = g[u][i];
        int weight = w[u];
        int pos = lower_bound(a, a + cnt, weight) - a + 1;
        add(pos, 1, i);
        dfs(v);
        add(pos, -1, i);
    }
}
int main()
{
    int T, u, v, fa, x;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        for(int i = 0; i <= n; i++) g[i].clear();
        cnt = 0;
        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &w[i]);
            a[cnt++] = w[i];
        }
        scanf("%d", &m);
        while(m--)
        {
            scanf("%d%d%d", &fa, &u, &v);
            g[fa].push_back(u);
            g[fa].push_back(v);
        }
        scanf("%d", &q);
        for(int i = 0; i <= q; i++) query[i].clear();
        for(int i = 0; i < q; i++)
        {
            scanf("%d%d", &v, &x);
            query[v].push_back(make_pair(i, x));
            a[cnt++] = x;
        }
        sort(a, a + cnt);
        cnt = unique(a, a + cnt) - a;
        memset(ta, 0, sizeof(ta));
        dfs(1);
        for(int i = 0; i < q; i++)
            if(ans[i][0] == -1)
                puts("0");
            else printf("%d %d\n", ans[i][1], ans[i][0]);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/sdj222555/article/details/9746127