시간 제한메모리 제한제출정답맞힌 사람정답 비율
8 초 1024 MB124433.333%

문제

$N$개의 정점과 $N-1$개의 간선으로 이루어진 트리가 있다. 각 정점에는 각각 $1$번부터 $N$번까지, 간선에는 $1$번부터 $N-1$번까지 번호가 붙어 있으며 모든 정점과 간선에는 가중치가 부여되어 있다. 이 때 다음의 쿼리를 처리하는 프로그램을 작성하시오.

  • $1$ $i$ $x$ : $i$번 정점의 가중치를 $x$로 변경한다.
  • $2$ $i$ $x$ : $i$번 간선의 가중치를 $x$로 변경한다.

최초 트리 상태와 각 변경 쿼리마다에 모든 $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$로 나눈 나머지를 출력한다.

예제 입력 1

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

예제 출력 1

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번

  • 문제를 검수한 사람: cs71107
  • 문제를 만든 사람: Lawali