트리와 쿼리 20

시간 제한5초메모리 제한512 MB

요약

동적으로 변하는 가중치 트리에서 정점 값을 토글하고, 각 트리에서 가중 거리 합이 최소인 정점의 값을 구하는 link-cut 자료구조 문제입니다.

난이도: 어려움10점 중 10점
유형: 트리, 세그먼트 트리, 유니온 파인드
정답자: 아직 제출이 없습니다

문제

$N$ \uAC1C\uC758 \uC815\uC810\uC73C\uB85C \uC774\uB8E8\uC5B4\uC9C4 \uD3EC\uB808\uC2A4\uD2B8\uAC00 \uC788\uB2E4. \uC815\uC810\uC740 $1$ \uBD80\uD130 $N$ \uAE4C\uC9C0 \uBC88\uD638\uAC00 \uB9E4\uACA8\uC838 \uC788\uACE0, \uCC98\uC74C\uC5D0\uB294 \uAC04\uC120\uC774 \uC5C6\uB2E4. \uAC01 \uC815\uC810 $v$ \uC5D0\uB294 \uC815\uC218 $X_v$ \uAC00 \uC788\uC73C\uBA70, \uCD08\uAE30\uAC12\uC740 \uBAA8\uB450 $1$ \uC774\uB2E4.

\uB2E4\uC74C \uCFFC\uB9AC\uB97C \uCC98\uB9AC\uD558\uB294 \uD504\uB85C\uADF8\uB7A8\uC744 \uC791\uC131\uD558\uC2DC\uC624.

1 a b c: \uC815\uC810 $a$ \uC640 \uC815\uC810 $b$ \uB97C \uAC00\uC911\uCE58 $c$ \uC778 \uAC04\uC120\uC73C\uB85C \uC5F0\uACB0\uD55C\uB2E4. \uC774 \uCFFC\uB9AC\uB294 \uC218\uD589\uD55C \uB4A4\uC5D0\uB3C4 \uC804\uCCB4 \uADF8\uB798\uD504\uAC00 \uD3EC\uB808\uC2A4\uD2B8\uC778 \uACBD\uC6B0\uC5D0\uB9CC \uC8FC\uC5B4\uC9C4\uB2E4.
2 a b: \uC815\uC810 $a$ \uC640 \uC815\uC810 $b$ \uB97C \uC787\uB294 \uAC04\uC120\uC744 \uC81C\uAC70\uD55C\uB2E4. \uC774 \uCFFC\uB9AC\uB294 \uB450 \uC815\uC810 \uC0AC\uC774\uC5D0 \uAC04\uC120\uC774 \uC788\uC744 \uB54C\uB9CC \uC8FC\uC5B4\uC9C4\uB2E4.
3 a: \uBA3C\uC800 $X_a$ \uB97C $1-X_a$ \uB85C \uBC14\uAFBC\uB2E4. \uADF8 \uB2E4\uC74C \uC815\uC810 $a$ \uAC00 \uC18D\uD55C \uD2B8\uB9AC\uC758 \uC815\uC810\uC744 $v_1, v_2, \dots, v_k$ \uB77C\uACE0 \uD560 \uB54C, \uC544\uB798 \uAC12\uC758 \uCD5C\uC19F\uAC12\uC744 \uCD9C\uB825\uD55C\uB2E4.

\min_{1 \le i \le k}\left\{ \sum_{1 \le j \le k} dist(v_i, v_j) \times X_{v_j} \right\}

\uC5EC\uAE30\uC11C $dist(v_i, v_j)$ \uB294 $v_i$ \uC5D0\uC11C $v_j$ \uB85C \uAC00\uB294 \uACBD\uB85C\uC5D0 \uC788\uB294 \uBAA8\uB4E0 \uAC04\uC120 \uAC00\uC911\uCE58\uC758 \uD569\uC774\uB2E4.

입력

\uCCAB\uC9F8 \uC904\uC5D0 \uC815\uC810\uC758 \uAC1C\uC218 $N$ \uACFC \uCFFC\uB9AC\uC758 \uAC1C\uC218 $Q$ \uAC00 \uC8FC\uC5B4\uC9C4\uB2E4. \uB458\uC9F8 \uC904\uBD80\uD130 $Q$ \uAC1C\uC758 \uC904\uC5D0 \uCFFC\uB9AC\uAC00 \uD55C \uC904\uC5D0 \uD558\uB098\uC529 \uC8FC\uC5B4\uC9C4\uB2E4.

\uCFFC\uB9AC\uC5D0 \uB4F1\uC7A5\uD558\uB294 \uC815\uC810 \uBC88\uD638\uB294 \uC554\uD638\uD654\uB418\uC5B4 \uC788\uC73C\uBBC0\uB85C, \uCFFC\uB9AC\uB97C \uC218\uD589\uD558\uAE30 \uC804\uC5D0 \uD574\uB3C5\uD574\uC57C \uD55C\uB2E4. \uC785\uB825\uC73C\uB85C \uC8FC\uC5B4\uC9C4 \uC815\uC810 \uBC88\uD638\uAC00 $x$ \uC774\uACE0 \uC9C0\uAE08\uAE4C\uC9C0 \uCC98\uB9AC\uD55C \uBAA8\uB4E0 $3$ \uBC88 \uCFFC\uB9AC\uC758 \uCD9C\uB825\uAC12 \uD569\uC774 $S$ \uB77C\uBA74, \uC2E4\uC81C \uC815\uC810 \uBC88\uD638\uB294 \uB2E4\uC74C\uACFC \uAC19\uB2E4.

(x - 1 + S) \bmod N + 1

\uCCAB \uBC88\uC9F8 $3$ \uBC88 \uCFFC\uB9AC \uC804\uC5D0\uB294 $S=0$ \uC73C\uB85C \uB454\uB2E4. $1$ \uBC88 \uCFFC\uB9AC\uC758 \uAC00\uC911\uCE58 $c$ \uB294 \uC554\uD638\uD654\uB418\uC9C0 \uC54A\uB294\uB2E4.

출력

$3$ \uBC88 \uCFFC\uB9AC\uC5D0\uC11C \uAD6C\uD55C \uAC12\uC744 \uCFFC\uB9AC\uAC00 \uC8FC\uC5B4\uC9C4 \uC21C\uC11C\uB300\uB85C \uD55C \uC904\uC5D0 \uD558\uB098\uC529 \uCD9C\uB825\uD55C\uB2E4.

제한

$1 \le N \le 10^5$
$1 \le Q \le 3 \times 10^5$
$1 \le a, b \le N$
$a \ne b$
$1 \le c \le 10^8$

예제3

예제 1

입력

예상 출력

4
0
0

예제 2

입력

예상 출력

예제 3

입력

10 37
1 2 3 6428496
1 7 10 41603701
1 2 7 61903527
1 1 6 57606292
1 2 1 43682226
1 8 2 59090781
3 6
3 10
1 10 7 15269842
3 6
3 7
1 3 10 39799671
1 3 5 28501778
3 5
2 1 10
1 6 10 37641690
2 9 6
3 8
1 6 8 89420938
3 9
2 6 3
1 9 6 17757145
2 9 3
1 1 9 26575112
2 3 8
1 2 1 19670627
2 3 5
1 1 5 12760556
2 3 4
1 4 1 36949637
3 7
2 6 9
1 6 8 74850387
2 3 8
3 3
1 7 3 77007154
3 3

예상 출력