---
# System prepended metadata

title: '#Subtask 1'

---

# Subtask 1:
* Với mỗi quy vấn duyệt qua mỗi đỉnh và chọn điểm đó là trạm tiếp nhận. 
* DFS từ điểm đó đến các điểm $k$ trạm để tính chi phí.
* Chọn ra trạm tiếp nhận có chi phí bé nhất.
* Độ phức tạp $\mathcal{O}(q⋅n^2)$.
# Subtask 2:
* với $k = 2$, mình chỉ cần tính chi phi từ đỉnh $s_{1}$ đến đỉnh $s_{2}$ bằng cách dùng lca.
* Độ phức tạp $\mathcal{O}(q⋅log(n))$.
# Subtask 3:
#### Với $k = 3$, mình sẽ lấy mọi cách chọn 2 đỉnh trong 3 đỉnh:
* Gọi đỉnh đầu là $x$ và đỉnh thứ 2 là $y$, mình sẽ có 2 bài toán subtask 2.
* Đầu tiên : tính chi phí của 2 đỉnh $x$ và $y$.
* Tiếp theo : gọi đỉnh lca của 2 đỉnh $x$ và $y$  là $z$. Tính chi phí từ đỉnh $z$ đến đỉnh còn lại (cách tính như subtask 2).
* chi phí cần tìm là tổng chi phí của 2 bài toán đó. 
* Đáp án là cách chọn 2 đỉnh có chi phí bé nhất.
* Độ phức tạp $\mathcal{O}(q⋅log(n))$.
# Subtask 4:
 Ở subtask này chúng ta chỉ có duy nhất một truy vấn. Cách tiếp cận đơn giản nhất là dp.
 * sử dụng dp Push_Up và Push_Down.
    * Lần DFS đầu tiên mình sẽ cập nhật từ cây con lên đỉnh cha của nó.
    * Lần DFS thứ hai mình sẽ cập nhật từ đỉnh cha đến các đỉnh con của nó dựa trên dữ liệu của lần DFS đầu tiên.
     
Dưới đây là code phần DFS ở sub này:
```cpp=
/*
 a[u] là danh sách kề của đỉnh u
 sight[u] = 1 khi đỉnh đó bật , ngược lại = 0;
 f[u] là chi phí từ các đỉnh con đến đỉnh u
 cnt[u] là số đỉnh bật trong cây con gốc u
 ct là số đỉnh bật ngoài cây con đang xét
 dis là chi phí của mọi đỉnh bật đến đỉnh đang xét
 */

typedef pair <int,int> ii;
void DFS_up(int u){
    cu[u] = sight[u]; f[u] = 0;
    for (ii v : a[u]){
        DFS_up(v.fi);
        f[u] += f[v.fi] + 1ll*cnt[v.fi]*v.se;
        cnt[u] += cnt[v.fi];
    }
}

void DFS_down(int u , long long dis , int ct){
    res = min(res,f[u] + dis);
    for (ii v : a[u]){
        int CNT = ct + cnt[u] - cnt[v.fi];
        long long DIS = dis + f[u] - f[v.fi] - 1ll*cnt[v.fi]*v.se + 1ll*CNT*v.se;
        DFS_down(v.fi,DIS,CNT);
    }
}

```
* Độ phức tạp $\mathcal{O}(n)$.
# Subtask 5:
#### Nhận xét : 
 * Trạm tiếp nhận luôn nằm trên lca của một trong tất cả các lca của 2 đỉnh bật bất kì. Lúc đó mình chỉ cần quan tâm đến các đỉnh bật và tất cả lca của nó. Khi đó chúng ta sẽ dp trên cây mới như subtask 4 khi cây đó chỉ gồm các đỉnh lca và các đỉnh trong tập hợp.
#### Ta có chứng minh: 
* lca của mọi cặp 2 đỉnh trong một tập hợp đỉnh sẽ luôn là các lca của 2 đỉnh liên tiếp sắp xếp theo thứ tự DFS.
 * https://codeforces.com/blog/entry/100910 : mục thứ $9$ của blog này đã chứng minh và cách dựng cây khi chỉ quan tâm đến lca và các đỉnh của tập hợp


#### Độ phức tạp: $\mathcal{O}(\sum_{j = 1}^{q}(k_{j} ⋅ log(k_{j})))$

#### Code mẫu :

```cpp=
//zuyvunee
#include <bits/stdc++.h>
#define All(x) (x).begin(),(x).end()
#define fi first
#define se second
using namespace std;
typedef pair <int,long long> ii;
const int N = 5e5 + 100;
const int LOG = 18;

int par[N][LOG + 2] , high[N] , sight[N];
long long pre[N];
int In[N] , Out[N] , cu[N] , cE = 0 , sz;
long long f[N] , res;
vector <int> node;
vector <ii> a[N];
vector <ii> b[N];
int n , q;

int lca(int u , int v){
    if (high[u] < high[v]) swap(u,v);
    for (int i = LOG ; i >= 0 ; i--) if (high[par[u][i]] >= high[v]) u = par[u][i];
    if (u == v) return u;
    for (int i = LOG ; i >= 0 ; i--) if (par[u][i] != par[v][i]){
        u = par[u][i]; v = par[v][i];
    }
    return par[u][0];
}

void dfs(int u){
    In[u] = ++cE;
    for (ii v : a[u]) if (v.fi != par[u][0]){
        pre[v.fi] = pre[u] + v.se;
        par[v.fi][0] = u;
        high[v.fi] = high[u] + 1;
        dfs(v.fi);
    }
    Out[u] = cE;
}

void DFSup(int u){
    cu[u] = sight[u]; f[u] = 0;
    for (ii v : b[u]){
        DFSup(v.fi);
        f[u] += f[v.fi] + 1ll*cu[v.fi]*v.se;
        cu[u] += cu[v.fi];
    }
}

void DFSdown(int u , long long dis , int cnt){
    res = min(res,f[u] + dis);
    for (ii v : b[u]){
        int CNT = cnt + cu[u] - cu[v.fi];
        long long DIS = dis + f[u] - f[v.fi] - 1ll*cu[v.fi]*v.se;
        DIS  += 1ll*CNT*v.se;
        DFSdown(v.fi,DIS,CNT);
    }
}

bool cmp(int x, int y) {return In[x] < In[y];}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen("txt.inp","r")){
        freopen("txt.inp","r",stdin);
        freopen("txt.out","w",stdout);
    }

    int n , q;
    cin >> n >> q;
    for (int i = 1 ; i < n ; i++){
        int x , y , z;
        cin >> x >> y >> z;
        a[x].push_back(ii(y,z));
        a[y].push_back(ii(x,z));
    }

    high[0] = -1;
    high[1] = 0;
    dfs(1);
    for (int j = 1 ; j <= LOG ; j++)
        for (int i = 1 ; i <= n ; i++)
            par[i][j] = par[par[i][j - 1]][j - 1];
    
    while (q--){
        cin >> sz;
        node.resize(sz);
        for (int &v : node){ cin >> v; sight[v] = 1;}
        sort(All(node),cmp);
        for (int i = 1 ; i < sz ; i++) node.push_back(lca(node[i - 1],node[i]));
        sort(All(node),cmp); node.resize(unique(All(node)) - node.begin());
        stack <int> p;
        p.push(node[0]);
        for (int i = 1 ; i < node.size() ; i++){
            while (true){
                int u = p.top();
                if (Out[u] >= In[node[i]]) break;
                p.pop();
            }
            b[p.top()].push_back(ii(node[i],pre[node[i]] - pre[p.top()]));
            p.push(node[i]);
        }

        DFSup(node[0]);
        res = 2e18;
        DFSdown(node[0],0,0);
        cout << res << "\n";

        for (int v : node){
            b[v].clear();
            sight[v] = 0;
        }
        node.clear();
    }
    return 0;
}

```