IOICamp::導遊讚哥讚！

IOICamp 2017，遇到的題目，應該也算是經典題。
給你一顆樹，會有人在上面移動，問你所有人到1號人的距離總和。
因為IOICamp Judge不公開就不放連結了。

題目其實就是這類題目的經典題「黑白點塗色」。
給你一顆樹，會把某些點塗成黑色或白色，問你所有黑點到某個點的距離和。
只要把所有人當作黑點，編號1的人特別處理。
紀錄所有人的位置，每次有人移動就把某個黑點刪掉然後再加回去，之後用編號1的人的位置去查詢答案就可以了，要注意每個點可能可以被塗黑很多次（或是說插入一個黑點可能比較貼切？）。
作法就是分治樹，也就是把樹分治的過程紀錄變成一顆樹的特別的資料結構。

雖然寫過了但是又忘記了QAQ。

分治樹的作法沒有很特別，重點是在怎麼處裡資料。
我覺的樹分治的關鍵就是 樹深度只有lgN 這點，所以利用這點進行更新和查詢就可以保證複雜度是好的。
以這題來說，對於每個分治樹上的點，我紀錄他們底下的黑點數量和到他們的父親的距離和，以及每個小孩的黑點數和和距離和。
有了這幾個資訊，每次我們想知道所有黑點到一個點的距離和，就可以用那些資訊推出來。當然這還要配合一些預處理的資訊像是每個點到他的「深度dep的祖先」的距離等等。

細節就在程式碼裡了。
比較有意思的事情是，我發現除了傳一個 reference 進去之外，用一個 static 變數也可以讓你在遞迴函數需要回傳多個資訊但是其實外面不需要的時候，讓code簡潔一點。
比如這裡找重心的 find_hr 函數，子樹的節點樹這個資訊就用了 tsz 這個變數來存，在函數return後馬上用另外一個變數接起來，而 sz 這個變數只有在 init = true 的時候初始化。
這樣子改的結果就是外面使用的時候只需要傳一個點，拿回來一個重心，也不需要額外的全域變數和reference就可以找重心了，跟之前的版本相比簡潔很多。

#include <bits/stdc++.h>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
using namespace std;
const int N = 1e4+1, lgN = 18;
typedef pair<int,long long> PIL;
vector<PIL> G[N];
struct htree{
    htree *fa;
    int sz, dep;
    PIL tofa, fromch;
    long long DIS[lgN];
    htree():fa(NULL),sz(0),dep(0),tofa(0,0),fromch(0,0){ }
}HT[N];
bool vis[N];
int count(int now, int no=-1){
    int cnt = 1;
    for(PIL v:G[now])if(v.first != no && !vis[v.first]){
        cnt += count(v.first,now);
    }
    return cnt;
}
int find_hr(int now, int no=-1, bool init=true){
    static int sz, tsz;
    if(init)sz = count(now,no);
    int tmx = 0, tsum = 0;
    for(PIL v:G[now])if(v.first != no && !vis[v.first]){
        int hr = find_hr(v.first, now, false);
        if(hr != -1)return hr;
        tsum += tsz;
        tmx = max(tmx, tsz);
    }
    tmx = max(tmx, sz-tsum-1);
    if(tmx <= sz/2)return now;
    tsz = tsum + 1;
    return -1;
}
void build_dep(int now,int no,int dep,long long dis){
    HT[now].DIS[dep] = dis;
    for(PIL v:G[now])if(v.first != no && !vis[v.first]){
        build_dep(v.first, now, dep, dis+v.second);
    }
}
int build_ht(int now, int dep=0){
    // cout<<"build_ht "<<now<<endl;
    int hr = find_hr(now);
    vis[hr] = 1;
    HT[hr].dep = dep;
    build_dep(hr,-1,dep,0);
    for(PIL v:G[hr])if(!vis[v.first]){
        int ch = build_ht(v.first, dep+1);
        HT[ch].fa = HT+hr;
    }
    return hr;
}
void update_ht(int now,int u){
    htree *ht = &HT[now];
    int dep = ht->dep;
    ht->sz += u;
    while(dep--){
        ht->tofa.first += u;
        ht->tofa.second += u*HT[now].DIS[dep];
        ht = ht->fa;
        ht->fromch.first += u;
        ht->fromch.second += u*HT[now].DIS[dep];
    }
}
long long query_ht(int now){
    htree *ht = &HT[now];
    int dep = ht->dep;
    long long res = HT[now].fromch.second;
    while(dep--){
        htree *fa = ht->fa;
        res += fa->fromch.second;
        res -= ht->tofa.second;
        res += (fa->fromch.first + fa->sz - ht->tofa.first)*HT[now].DIS[dep];
        ht = fa;
    }
    return res;
}
int pos[N];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t,n,m,k,a,b,c;
    cin>>t;
    while(t--){
        fill(HT,HT+N,htree());
        memset(pos,0,sizeof(pos));
        memset(vis,0,sizeof(vis));
        fill(G,G+N,vector<PIL>());
        cin>>n>>m>>k;
        F(n-1){
            cin>>a>>b>>c;
            a--;b--;
            G[a].push_back(PIL(b,c));
            G[b].push_back(PIL(a,c));
        }
        build_ht(0);
        update_ht(0,m-1);
        F(k){
            cin>>a>>b;
            a--;b--;
            if(a == 0){
                pos[0] = b;
            }else{
                update_ht(pos[a],-1);
                pos[a] = b;
                update_ht(pos[a],1);
            }
            cout<<query_ht(pos[0])<<endl;
        }
    }
}