시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 (추가 시간 없음) 1024 MB 34 7 6 24.000%

문제

You are given a tree with $N$ vertices. Vertices are indexed from $1$ to $N$. The tree is vertex-weighted. In other words, each vertex of the tree is assigned a nonnegative integer weight.

We will delete some edges from the tree. After the deletion, for each connected component, the sum of vertex weights should be in the range $[L, R]$. 

For all integers $0 \le i \le K$, determine if we can achieve this goal by deleting exactly $i$ edges.

입력

The first line contains a single integer $T$, the number of test cases. $T$ test cases follow, each following the given specification:

The first line contains four integers $N$, $K$, $L$, and $R$.

The next line contains $N$ integers $A_1, A_2, \ldots, A_N$, where $A_i$ denotes the weight of vertex $i$.

The next $N-1$ lines contain two integers $x, y$, denoting the pair of vertices connected by an edge.

출력

For each test case, output a binary string of length $K + 1$. The $i$-th character should be 1 if it is possible to achieve the desired goal by deleting exactly $i-1$ edges. Otherwise, the $i$-th character should be 0.

제한

  • $1 \le N \le 1\,000$
  • $0 \le K \le \min(50, N - 1)$
  • $0 \le L \le R \le 10^{18}$
  • $0 \le A_i \le 10^{18}$
  • $1 \le x, y \le N$
  • $x \neq y$
  • The given graph is a tree.
  • For all test cases, the sum of $N$ is at most $1\,000$.

서브태스크 1 (9점)

This subtask has an additional constraint:

  • $N \le 10$

서브태스크 2 (24점)

This subtask has an additional constraint:

  • $R \le 50$

서브태스크 3 (10점)

This subtask has an additional constraint:

  • $y = x + 1$ for all edges in the tree.

서브태스크 4 (57점)

This subtask has no additional constraints.

예제 입력 1

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

예제 출력 1

0111
0011
0000

출처

University > KAIST > 2021 KAIST RUN Spring Contest H번

채점 및 기타 정보

  • 예제는 채점하지 않는다.