시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 (추가 시간 없음) | 1024 MB | 69 | 21 | 19 | 33.929% |
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
.
This subtask has an additional constraint:
This subtask has an additional constraint:
This subtask has an additional constraint:
This subtask has no additional constraints.
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
0111 0011 0000
University > KAIST > 2021 KAIST RUN Spring Contest H번
Camp > Petrozavodsk Programming Camp > Winter 2022 > Day 2: Grand Prix of Daejeon K번
Contest > Open Cup > 2021/2022 Season > Stage 11: Grand Prix of Daejeon K번