---
author: little
tags: msttn
title: msttn Solution
---

$\Huge\text{msttn Solution}$

-------

:::info
📌 Tags: `binary search` `greedy` `sorting`
✍️ Writer: little
📋 Content:
[TOC]
:::

-----

## Thuật toán

Ta sẽ biến đổi trọng số của mỗi cạnh $(i, j)$ như sau:
$w_i * w_j + t * (w_i + w_j)$ $=$ $w_i * w_j + w_i * t + w_j * t + t^2 - t^2$ $=$ $(w_i + t) * (w_j + t) - t^2$

Ban đầu ta sẽ sắp xếp tăng dần mảng $w$. Nhận xét là ta sẽ luôn luôn chọn đúng $n - 1$ cạnh để tạo cây khung. Với mỗi truy vấn, ta sẽ xét:
- Nếu $w_1 + t \geq 0$ thì ta sẽ nối đỉnh $1$ với $n - 1$ đỉnh còn lại. Kết quả sẽ là: $(w_1 + t) * (pref_n - pref_1 + t * (n - 1)) - t^2 * (n - 1)$
- Nếu $w_n + t < 0$ thì ta sẽ nối đỉnh $n$ với $n - 1$ đỉnh còn lại. Kết quả sẽ là: $(w_n + t) * (pref_{n-1} + t * (n - 1)) - t^2 * (n - 1)$
- Nếu không tồn tại $2$ trường hợp trên thì cách chọn tối ưu của ta sẽ là: nối đỉnh $1$ với đỉnh $n$, chặt nhị phân tìm $ind$ là vị trí trái cùng sao cho $w_{ind} + t \geq 0$. Ta sẽ nối đỉnh $1$ với các đỉnh từ $ind...n-1$ và nối đỉnh $n$ với các đỉnh từ $2...ind-1$.

----

Tham khảo code ở [đây](https://ideone.com/0wmt2v)