[HDU 7136] Jumping Monkey | 并查集 | 逆向思维

Jumping Monkey

Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)

Total Submission(s): 747 Accepted Submission(s): 360

Problem Description

There is a tree with n nodes and n−1 edges that make all nodes connected. Each node i has a distinct weight ai. A monkey is jumping on the tree. In one jump, the monkey can jump from node u to node v if and only if av is the greatest of all nodes on the shortest path from node u to node v. The monkey will stop jumping once no more nodes can be reached.

For each integer k ∈ [ 1 , n ] k∈[1,n]k∈[1,n], calculate the maximum number of nodes the monkey can reach if he starts from node k.

Input

The first line of the input contains an integer T (1≤T≤104), representing the number of test cases.

The first line of each test case contains an integer n (1≤n≤105), representing the number of nodes.

Each of the following n−1 lines contains two integers u,v ( 1 ≤ u , v ≤ n ) , representing an edge connecting node u and node v. It is guaranteed that the input will form a tree.

The next line contains n distinct integers a1,a2,…,an (1≤ai≤109), representing the weight of each node.

It is guaranteed that the sum of n over all test cases does not exceed 8×105.

Output

For each test case, output n lines. The k-th line contains an integer representing the answer when the monkey starts from node k.

Sample Input

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

Sample Output

3
2
1
4
2
3
1
3

Hint

For the second case of the sample, if the monkey starts from node 1 11, he can reach at most 4 44 nodes in the order of 1 → 3 → 2 → 4 1 \to 3 \to 2 \to 41→3→2→4.

#define lowbit(x) (x & (-x))
#define Clear(x,val) memset(x,val,sizeof x)
vector<int> vet[maxn];
vector<int> after[maxn];/// save the ans tree
int fa[maxn], n;
bool vis[maxn];
void init() {
  for (int i = 1; i <= n; i++) {
    fa[i] = i, vis[i] = 0;
    vet[i].clear();
    after[i].clear();
  }
}
int find(int x) {
  if (x == fa[x]) return x;
  else return fa[x] = find(fa[x]);
}
typedef pair<ll, int> PII;
PII a[maxn];
int ans[maxn];
void getDepth(int cur, int faNode, int depth) {
  ans[cur] = depth;
  for (int to : after[cur]) {
    if (to == faNode) continue;
    getDepth(to, cur, depth + 1);
  }
}
int main() {
  int _ = read;
  while (_--) {
    n = read;
    init();
    for (int i = 1; i < n; i++) {
      int u = read, v = read;
      vet[u].push_back(v);
      vet[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
      a[i].first = read;
      a[i].second = i;
    }
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i++) {
      int u = a[i].second;
      for (int v : vet[u]) {
        if (vis[v]) {
          int fav = find(v);
          fa[fav] = u;
          after[u].push_back(fav);
        }
      }
      vis[u] = 1;
    }
    getDepth(a[n].second, 0, 1);
    for (int i = 1; i <= n; i++) printf("%d\n", ans[i]);
  }
  return 0;
}
/**
2
3
1 2
2 3
1 2 3
5
1 2
1 3
2 4
2 5
1 4 2 5 3
**/