HDU 5678 ztr loves trees

Problem Description

Super Deity ztr likes trees from childhood,CCTV-children:"The apple on the apple tree.You and I under the apple tree.Play games in front of the apple tree.So many happiness".

One day,qzh visit ztr to ask some questions.To give a tree with a root,each vertex has a value.Each time query the median of a subtree.

ztr said:this is a water problem,do you do it?But qzh show cannot help but want you who is also a Super Deity to help him.Could you help him?

Input

There are T test cases. The first line of input contains an positive integer T indicating the number of test cases.

For each test case:

Each line contains two positive integer n,m.indicating the number of vetrex and the number of query times.

The next line contains n numbers, the ith number indicating the value of vertex i.

The next n-1 lines,each line contains two numbers u and v,indicating there is a edge form u to v.

The next m lines, each line contains a numbers x.indicating query the median of subtree x.

1<=T<=3,1<=n<=105,1<=m<=106,1<=u<=v<=n,1<=val<=109.

The vetrex 1 is the root of the tree.Guarantee input a tree with a root.

Output

For each test case:print a line.To avoid huge output,you should hash each answer first,then print it.

The method to hash:a[i] indicates the ith query result,

ans=∑a[i]∗10m−imod1,000,000,007 Round to the nearest tenth

Sample Input

1

5 3

1 2 3 4 5

1 2

2 3

3 4

4 5

1

2

3

Sample Output

339.0

先從樹形轉線形，然後是區間第k大即可。

這題資料有問題，val有等于0的,我寫的不是離散的是以一直wa,簡直有毒。

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef unsigned long long LL;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;
int T, n, m, v[maxn], x, y;
int ft[maxn], nt[maxn], u[maxn], sz;
int now[maxn], tot;
double ans[maxn];

struct Tree
{
  int f[maxn << 6], L[maxn << 6], R[maxn << 6];
  int root[maxn], sz;
  int Node() { f[sz] = L[sz] = R[sz] = 0; return sz++; }
  void clear() { sz = 1; root[0] = 0; }
  void add(int bef, int now, int l, int r, int v)
  {
    L[now] = L[bef];    R[now] = R[bef];    f[now] = f[bef] + 1;
    if (l == r) return;
    int m = l + r >> 1;
    if (v <= m)
    {
      L[now] = Node();
      add(L[bef], L[now], l, m, v);
    }
    else
    {
      R[now] = Node();
      add(R[bef], R[now], m + 1, r, v);
    }
  }
  void insert(int rt, int v)
  {
    root[rt] = Node();
    add(root[rt - 1], root[rt], 0, 1e9, v);
  }
  double find(int bef, int now, int l, int r, int v)
  {
    if (l == r) return l;
    int m = l + r >> 1;
    if (f[L[now]] - f[L[bef]] >= v) return find(L[bef], L[now], l, m, v);
    return find(R[bef], R[now], m + 1, r, v - f[L[now]] + f[L[bef]]);
  }
  double get(int r1, int r2)
  {
    if ((r2 - r1) & 1) return find(root[r1], root[r2], 0, 1e9, r2 - r1 + 1 >> 1);
    return (find(root[r1], root[r2], 0, 1e9, r2 - r1 >> 1) + find(root[r1], root[r2], 0, 1e9, r2 - r1 + 2 >> 1)) / 2.0;
  }
}solve;

void dfs(int x)
{
  solve.insert(now[x] = ++tot, v[x]);
  for (int i = ft[x]; i != -1; i = nt[i]) dfs(u[i]);
  ans[x] = solve.get(now[x] - 1, tot);
}

int main()
{
  scanf("%d", &T);
  while (T--)
  {
    scanf("%d%d", &n, &m);
    tot = sz = 0;
    for (int i = 1; i <= n; i++)
    {
      scanf("%d", &v[i]);
      ft[i] = -1;
    }
    for (int i = 1; i < n; i++)
    {
      scanf("%d%d", &x, &y);
      u[sz] = y; nt[sz] = ft[x]; ft[x] = sz++;
    }
    solve.clear();     dfs(1);
    double res = 0;
    while (m--)
    {
      scanf("%d", &x);
      res = fmod(res * 10 + ans[x], mod);
    }
    printf("%.1lf\n", res);
  }
  return 0;
}