Code 備忘錄►Divide & Conquer

TIOJ::ZJOI::1844 . 幻想乡战略游戏

http://tioj.ck.tp.edu.tw/problems/1844
這題是大陸的OI題，跟樹分治有關，但是又進階了一點。
有點難寫，但是Code沒有很長，寫之前最好想清楚再下手可以省下一些不必要的Debug時間。

這題是ZJOI 2015的題目，ZJOI應該是大陸某個省的OI選拔，可能是浙江吧？

題目給你一棵樹，樹上每個點都有一些士兵，每個點之間有一個距離。你可以在某個點上設置補給站，補給的費用就是每個士兵到補給站的距離和，求最好的設置位置下，最低的花費是多少？題目還會更新每個點的士兵數量，可能會增加或是減少，每次更新完你就要輸出當前的最少花費是多少。

這題聽起來就有樹分治的感覺，但是題目有很多的更新，所以我們不能每次都樹分治一次，那怎麼辦？
這時候可以想到一個很顯然的作法（真的很顯然喔，自己可以想到那種），就是先把樹分治的過程存起來，然後每次更新，查詢。因為樹分治深度會小於$logN$，這樣就保證複雜度是$O(N logN)$。
於是我們就建了一顆重心樹，並維護這棵重心樹上的答案，然後對他做查詢。大陸的題解都叫他動態重心剖分或是動態（樹）點分治的樣子。

那實際怎麼做呢？
對於一個重心（以下稱為CBD），我們可以紀錄他的每棵子樹有幾個士兵、和目前的答案是多少（每個士兵到這個CBD的距離和），然後我們可以發現，如果這個點不是答案，答案一定存在士兵數最多的子樹中！！
這點其實很好想，如果把補給站從這個CBD移到某個子樹中，就等同把現在這個點當成一個新的子樹，這個新子樹的點數將會是除了原本那個子樹裡面的士兵A之外的所有士兵A’，而我們往子樹內移動經過的這條邊，需要經過這條邊的士兵數也會從A變成A’，所以我們發現，答案會在某個子樹內若且唯若那個子樹的士兵數量大於全部士兵的一半！否則你往該子樹移動一格，會經過你走的這條邊的士兵數反而會變多，總花費就上升了。所以實際上我們就選擇子樹士兵最多的走就好。
但是遞迴進去之後，子樹的答案就不是整顆樹的答案了，所以我們必須要把現在這個CBD的所有士兵數和目前的答案，扣掉我們要檢查的那棵子樹然後傳進去遞迴，在裡面我們要把這些值加到子樹的子樹上，以維護他是整顆樹的答案。
為了維護這件事，我們要紀錄每個子樹會連到哪些祖先（不包含自己），因為分治樹的子樹，同一個深度的祖先只會最多連到一個，所以紀錄連到哪個深度的祖先就可以了。然後在找答案的時候，就分別紀錄每個深度的祖先的數值是多少，再個別處理。要注意有些祖先不是接在子樹上而是直接接在子樹的重心CBD上，所以要另外檢查和自己重心相鄰的點哪些是自己的祖先，直接加入總和裡，這樣之後的遞迴答案才會是對的。
其實基本上就是亂做搞一搞該維護的維護一下就會AC了。注意數字範圍，小心溢位。
我用到的東西包含：原本的樹、重心樹、每個點到某一層祖先的距離、每個重心樹節點的士兵數和這些士兵到他父親的距離和。

這東西實在很難講，除了掌握答案一定在士兵數最多的點數還有利用點分治樹讓樹高低於 logN 之外，其他的大概要自己畫圖思考一遍比較好理解。

關於樹分治，有一題之前寫過的題目
所謂的樹重心就是讓最大的子樹最小的那個點，用這個點去切樹，可以保證樹的大小都小於 logN （你可以用一條鍊去想就會明白了）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#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 = 1e5+1;
typedef pair<int,int> PII;
typedef pair<int,long long> PIL;
struct CBD{
    vector<int>ch,prt;
    int fa,dri,sz;
    long long dp;
    CBD():fa(-1),sz(0),dp(0){}
}TR[N];
bool wed[N];
vector<PII> G[N];
vector<int> DR[N];
int SZ[N];
int count_n(int now, int no, int dr, vector<int>&prt){
    int sum = 0;
    DR[now].push_back(dr);
    for(PII p:G[now])if(p.first!=no){
        if(wed[p.first]){
            prt.push_back(TR[p.first].dri);
        }else{
            sum += count_n(p.first,now,dr+p.second,prt);
        }
    }
    return sum+1;
}
int find_heart(int now, int no, int&h, int&hmx, int n){
    int sum = 0, mx = 0;
    for(PII p:G[now])if(p.first!=no&&!wed[p.first]){
        int tmp = find_heart(p.first,now,h,hmx,n);
        mx = max(mx, tmp);
        sum += tmp;
    }
    if(hmx > max(sum, n-sum))h = now, hmx = max(sum, n-sum);
    return sum + 1;
}
int tree_fun_jizz(int now, int dri, int n){
    int hrt,tmp = 2147483647;
    find_heart(now,-1,hrt,tmp,n);
    wed[hrt] = true;
    TR[hrt].dri = dri;
    for(PII p:G[hrt])if(!wed[p.first]){
        vector<int> prt;
        int chh = tree_fun_jizz(p.first,dri+1,count_n(p.first,hrt,p.second,prt));
        TR[hrt].ch.push_back(chh);
        TR[chh].fa = hrt;
        TR[chh].prt = prt;
    }
    return hrt;
}
void update(int x,int u){
    SZ[x] += u;
    int p = DR[x].size();
    int now = x;
    while(p--){
        TR[now].sz += u;
        TR[now].dp += 1ll*DR[x][p]*u;
        now = TR[now].fa;
    }
}
long long find_ans(int now, vector<PIL>&ES){
    long long mxdp = 0, sumdp = 0;
    int mxsz = 0, mxp = -1, sumsz = 0;
    for(PII pr:G[now])if(TR[now].dri>TR[pr.first].dri){
        int pdri = TR[pr.first].dri;
        sumsz += ES[pdri].first;
        sumdp += 1ll*ES[pdri].first*DR[now][pdri] + ES[pdri].second;
    }
    for(int p:TR[now].ch){
        long long dp = TR[p].dp;
        int sz = TR[p].sz;
        for(int i:TR[p].prt){
            assert(i>=0&&i<ES.size());
            dp += 1ll*ES[i].first*DR[now][i]+ES[i].second;
            sz += ES[i].first;
        }
        sumsz += sz;
        sumdp += dp;
        if(sz > mxsz)mxdp = dp, mxp = p, mxsz = sz;
    }
    ES.push_back(PIL(sumsz-mxsz+SZ[now], sumdp-mxdp));
    if(mxp!=-1)return min(sumdp, find_ans(mxp,ES));
    return sumdp;
}
main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,q,rt,a,b,c;
    cin>>n>>q;
    F(n-1){
        cin>>a>>b>>c;
        G[a].push_back(PII(b,c));
        G[b].push_back(PII(a,c));
    }
    rt = tree_fun_jizz(1,0,n);
    while(q--){
        cin>>a>>b;
        update(a,b);
        vector<PIL> tmp;
        cout<<find_ans(rt,tmp)<<endl;
    }
}