31820번 - Tree Kadane 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 109 | 24 | 19 | 27.941% |
문제
$1$부터 $N$까지 번호가 매겨진 $N$개의 정점으로 이루어진 트리 $T$가 주어진다. 각 $i$번 정점은 정수 가중치 $A_i$를 가진다.
$T$의 연결 부분 집합 $S$는 $T$의 정점들의 공집합이 아닌 부분 집합으로, $S$에 속하는 두 정점 $a$, $b$에 대해 $S$에 속한 정점만을 사용하는 $a$에서 $b$로 가는 경로가 $T$에 존재한다.
다음 $Q$개의 쿼리를 처리해야 한다.
- $k$ $x$: $A_k$를 $x$로 바꾸고 $T$의 연결 부분 집합 $S$에 대한 $\sum_{i\in S}{A_i}$의 최댓값을 출력한다.
입력
첫 번째 줄에 정점의 개수를 나타내는 정수 $N$이 주어진다.
두 번째 줄에 각 정점의 가중치를 나타내는 $N$개의 정수 $A_1,A_2,\dots ,A_N$이 공백으로 구분되어 주어진다.
다음 $N-1$개의 줄 중 $i$번째 줄에 두 정수 $u_i$와 $v_i$가 공백으로 구분되어 주어진다. 이들은 $i$번째 간선의 양 끝 점을 나타낸다.
다음 줄에 쿼리의 개수를 나타내는 정수 $Q$가 주어진다.
다음 $Q$개의 줄에 걸쳐 각 줄에 각 쿼리를 나타내는 두 정수 $k$와 $x$가 공백으로 구분되어 주어진다.
출력
$Q$개의 줄에 걸쳐 쿼리의 정답을 한 줄에 하나씩 출력한다.
제한
- $1\leq N\leq 10^5$
- $-10^9\leq A_i\leq 10^9$ ($1\leq i\leq N$)
- $1\leq u_i,v_i\leq N$ ($1\leq i\leq N-1$)
- 주어지는 그래프는 트리이다.
- $1\leq Q\leq 10^5$
- 각 쿼리에 대해 $1\leq k\leq N$
- 각 쿼리에 대해 $-10^9\leq x\leq 10^9$
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | $N, Q \leq 10^3$ |
| 2 | 20 | 각 정점의 차수는 $3$ 미만이다. |
| 3 | 70 | 추가적인 제약 조건이 없다. |
예제 입력 1
5 3 -1 -4 -1 -5 1 2 1 3 3 4 3 5 5 1 -2 3 2 4 1 2 5 1 -9
예제 출력 1
-1 2 3 6 5
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호