(IOICamp_Judge) 導遊讚哥讚！ [重心剖分]

https://judge.ioicamp.org/problems/78

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <vector>
#include <utility>
#include <algorithm>
#include <cassert>
using namespace std;

#define int long long

typedef long long LL;
const int MAX_N = 1e4 +6;
const int MAX_M = 1e4 +6;
const int MAX_P = 18;

struct Edge {
    int to;
    LL w;
    void _() {
        cout<<"to = "<<to<<" , w = "<<w<<endl;
    }
};

Edge MP(int _to,LL _w) {
    return Edge{_to,_w};
}

vector<Edge> edg[MAX_N];

struct Cen {
    int par;
    LL add;
    LL minus;
    int sz;
    void _() {
        cout<<"par = "<<par<<" , add = "<<add<<" , minus = "<<minus<<" , sz = "<<sz<<endl;
    }
} cen[MAX_N];

int now[MAX_N];
int depth[MAX_N];
Edge lca[MAX_P][MAX_N];
bool visit[MAX_N];
int stamp;
int tin[MAX_N],tout[MAX_N];

void dfs1(int id,int p,LL w,int cur_depth) {
    tin[id] = stamp++;
    visit[id] = 1;
    lca[0][id] = MP(p,w);
    depth[id] = cur_depth;
    for (auto i:edg[id]) {
        if (!visit[i.to]) {
            dfs1(i.to,id,i.w,cur_depth+1);
        }
    }
    tout[id] = stamp++;
}

vector<int> v;
int sz[MAX_N];
int mx[MAX_N];

void dfs3(int id) {
    visit[id]=1;
    sz[id]=1;
    mx[id]=0;
    v.push_back(id);
    for (auto i:edg[id]) {
        if (!visit[i.to]) {
            dfs3(i.to);
            sz[id] += sz[i.to];
            mx[id] = max(mx[id],sz[i.to]);
        }
    }
}

Cen MP4(int par,LL add,LL minus,int sz) {
    return Cen{par,add,minus,sz};
}

void dfs2(int id,int par_cen) {
    v.clear();
    dfs3(id);
    int can=-1;
    int tot=v.size();
    for (auto i:v) {
        visit[i]=0;
        if (max(mx[i],tot-sz[i]) <= tot/2) {
            can = i;
        }
    }
    visit[can]=true;
    cen[can] = MP4(par_cen,0,0,0);
    for (auto i:edg[can]) {
        if (!visit[i.to]) {
            dfs2(i.to,can);
        }
    }
}

bool is_anc(int son,int parent) {
    return tin[son] >= tin[parent] && tout[son] <= tout[parent];
}

LL get_dis(int x,int y) {
    if (depth[x] > depth[y]) swap(x,y);
    if (x==y) return 0;
    //x is lower
    if(is_anc(y,x)) {
        //we need only from y to x
        LL ret=0;
        for (int i=MAX_P-1;i>=0;i--) {
            if (!is_anc(x,lca[i][y].to)) {
                ret += lca[i][y].w;
                y = lca[i][y].to;
            }
        }
        ret += lca[0][y].w;
        return ret;
    }
    else {
        int tx=x,ty=y;
        x=tx,y=ty;
        LL ret=0;
        for (int i=MAX_P-1;i>=0;i--) {
            if (!is_anc(x,lca[i][y].to)) {
                ret += lca[i][y].w;
                y = lca[i][y].to;
            }
        }
        ret += lca[0][y].w;
        x=ty,y=tx;
        for (int i=MAX_P-1;i>=0;i--) {
            if (!is_anc(x,lca[i][y].to)) {
                ret += lca[i][y].w;
                y = lca[i][y].to;
            }
        }
        ret += lca[0][y].w;
        return ret;
    }
}

void add(int id) {
    int now=id;
    while (now != -1) {
        cen[now].add += get_dis(now,id);
        cen[now].sz++;
        if (cen[now].par == -1) break;
        cen[now].minus += get_dis(cen[now].par,id);
        now = cen[now].par;
    }
}

void deleted(int id) {
    int now=id;
    while (now != -1) {
        cen[now].add -= get_dis(now,id);
        cen[now].sz--;
        if (cen[now].par == -1) break;
        cen[now].minus -= get_dis(cen[now].par,id);
        now = cen[now].par;
    }
}

LL query(int id) {
    int now=id;
    LL ret=0;
    int totsz=0;
    while (now != -1) {
        ret += (cen[now].add - cen[now].minus);
        ret += (cen[now].sz - totsz)*get_dis(id,now);
        totsz = cen[now].sz;
        now = cen[now].par;
    }
    return ret;
}

main () {
    int T;
    scanf("%lld",&T);
    while (T--) {
        int n,m,q;
        scanf("%lld %lld %lld",&n,&m,&q);
        for (int i=0;n>=i;i++) {
            edg[i].clear();
        }
        for (int i=1;n>i;i++) {
            int a,b,c;
            scanf("%lld %lld %lld",&a,&b,&c);
            edg[a].push_back(MP(b,c));
            edg[b].push_back(MP(a,c));
        }
        stamp=0;
        memset(visit,0,sizeof(visit));
        dfs1(1,1,0,1);
        for (int i=1;MAX_P>i;i++) {
            for (int j=1;n>=j;j++) {
                lca[i][j] = MP(lca[i-1][lca[i-1][j].to].to,lca[i-1][j].w+lca[i-1][lca[i-1][j].to].w);
            }
        }
        memset(visit,0,sizeof(visit));
        dfs2(1,-1);
        now[1]=1;
        for (int i=2;m>=i;i++) {
            add(1);
            now[i]=1;
        }
        while (q--) {
            int a,b;
            scanf("%lld %lld",&a,&b);
            if (a==1) {
                now[a]=b;
            }
            else {
                deleted(now[a]);
                now[a]=b;
                add(now[a]);
            }
            LL ret=query(now[1]);
            printf("%lld\n",ret);
            assert(ret>=0);
        }
    }
}