시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
8 초 | 1024 MB | 12 | 4 | 4 | 33.333% |
$N$개의 정점과 $N-1$개의 간선으로 이루어진 트리가 있다. 각 정점에는 각각 $1$번부터 $N$번까지, 간선에는 $1$번부터 $N-1$번까지 번호가 붙어 있으며 모든 정점과 간선에는 가중치가 부여되어 있다. 이 때 다음의 쿼리를 처리하는 프로그램을 작성하시오.
최초 트리 상태와 각 변경 쿼리마다에 모든 $N(N-1)/2$개의 서로 다른 경로에 대하여 (경로 상의 정점 가중치의 합)$\times$(경로 상의 간선 가중치의 합)의 합을 $10^9+7$로 나눈 나머지를 출력하시오.
첫째 줄에 정점의 수와 쿼리의 수 $N$과 $Q$가 공백을 사이에 두고 주어진다. ($2 \leq N \leq 2
\times 10^5, 1 \leq Q \leq 2 \times 10^5$)
둘째 줄에 i번째 정점의 가중치 $A_i$가 공백을 사이에 두고 주어진다. ($1 \leq A_i \leq 10^9$)
셋째 줄부터 $N+1$번째 줄까지 $i$번째 간선의 정보를 의미하는 세 정수 $u_i$ $v_i$ $w_i$가 공백을 사이에 두고 주어진다. 정점 $u_i$와 정점 $v_i$ 사이에 가중치가 $w_i$인 간선이 존재한다는 의미이다.
$N+2$번째 줄부터 $N+Q+1$번째 줄까지 각 쿼리의 정보 $t$ $i$ $x$가 공백을 사이에 두고 주어진다.
$t=1$ or $2$이며 $t=1$일 경우 $1 \leq i \leq N$이고 $t=2$일 경우 $1 \leq i \leq N-1$이고, $1 \leq x \leq 10^9$이다.
$Q+1$개의 줄에 걸쳐 정답을 $10^9+7$로 나눈 나머지를 출력한다.
3 2 1 2 3 1 2 1 2 3 2 1 1 3 2 2 4
31 39 65
1-2의 경로, 2-3의 경로, 1-3의 경로가 존재한다.
첫번째 출력 : $(1+2) \times 1+(2+3) \times 2+(1+2+3) \times (1+2)=31$
두번째 출력 : $(3+2) \times 1+(2+3) \times 2+(3+2+3) \times (1+2)=39$
세번째 출력 : $(3+2) \times 1+(2+3) \times 4+(3+2+3) \times (1+4)=65$
University > 고려대학교 > 2021 고려대학교 프로그래밍 경시대회 (KCPC) > Div. 1 F번