Advanced Tree Algorithm

給你一棵有 \(N\) 個點的樹，求樹上全點對距離總和

即求 \(\sum\limits_{i=1}^{n} \sum\limits_{j=i+1}^{n} length(i,j)\)

以上圖為例總合為
(1+1+1+2)+(1+2+2+3)+(1+2+2+1)+(1+2+2+3)+(2+3+1+3) = 36

找一個點 (這邊以節點1為根) 當根，
算出所有點的子樹到自己的距離總和

遞迴到每個點順便算每個點到當前點的距離

算每個節點的子樹到自己的距離總和，以及子樹大小
dp[i] 的定義為以節點i為根的子樹到節點i的距離總和

dp[1] = dp[2] + dp[3] + dp[4] + (sz[1]-1) = 5
dp[2] = 0
dp[3] = dp[5] + (sz[3]-1) = 1
dp[4] = 0
dp[5] = 0

從根節點開始算每個節點到自己的距離總和
根節點1到每個節點的距離總和就是 dp[1]

從根結點遞迴下去到節點3，這時我們會傳一個參數下去
從父節點方向來的節點到當前節點距離總和
也就是 (dp[1]-(dp[3]+sz[3])) + dp[3] + (sz[1]-sz[3])

( 父節點方向到節點3的距離總和 + 自己子樹到節點3距離總和 + 父節點方向的節點數量 )

每次合併時，把小的往大的合併
先來看以下兩種極端例子

其中一邊的樹比另一邊大很多，
當小的合併到大的時候複雜度趨近於常數

當兩邊大小差不多時，
合併的複雜度為 \(O(n)\) (n為樹的大小)

因此可以發現兩種情況中，如果每次合併都是第一種
把小的合併到大的，那均攤複雜度為 \(O(N)\)

但如果每次都是第二種，複雜度會變多少?

因此透過每次小的合併到大的
最差複雜度為 \(O(NlgN)\)

當需要用到子樹的資訊，每次去合併時
如果每次都把小的合併到大的，最差複雜度 \(O(NlgN)\)

用一個map紀錄不同顏色的數量

最差情況：每個節點顏色都不同
照子樹大小去合併，複雜度為 \(O(NlgNlgN)\)
啟發式合併 \(O(NlgN)\) * map複雜度 \(O(lgN)\)

記得正常情況下的並查集，只需使用路徑壓縮即可

除非是需要用到 啟發式合併的技巧 或者 持久化並查集
再用啟發式合併

重兒子：每個點的子樹中，子樹大小(即節點數)最大的子節點

輕兒子：除重兒子外的其他子節點

重邊：每個節點與其重兒子間的邊

輕邊：每個節點與其輕兒子間的邊

重鏈：重邊連成的鏈

輕鏈：輕邊連成的鏈

//假設1-base，並且0為指向空節點,sz[0]=0
void dfs1(int x,int f,int d){
    depth[x]=d;  //紀錄深度
    father[x]=f; //設父節點
    sz[x]=1;     //將自己本身加進子樹大小
    son[x]=0;    //一開始先指向空
    for(int i=0;i<edge[x].size();i++){
        if(edge[x][i]==f)    continue;
        dfs1(edge[x][i],x,d+1);        //dfs下去紀錄每個子樹的大小
        sz[x]+=sz[edge[x][i]];         //將子樹大小加至自己
        if(sz[edge[x][i]]>sz[son[x]])  son[x]=edge[x][i];  //找重兒子
    }
}
 

int treeSz=1;
void dfs2(int x,int f){
    for(int i=0;i<edge[x].size();i++){
        if(edge[x][i]==f)    continue;
        if(edge[x][i]==son[x])            //判斷是否為重兒子
            root[edge[x][i]]=root[x];     //若為重兒子則將連至上面的鏈
        else    root[edge[x][i]]=edge[x][i],treeSz++; //否則剖分成新鏈
        dfs2(edge[x][i],x);
    }
    len[root[x]]++;                      //更新每條鏈的長度
}
 

vector<int> treeID;
vector<vector<int>> tree;
void buildEachTree(){
    tree.resize(treeSz);
    for(int i=1,j=0;i<=n;i++){
        if(root[i]==i){    //判斷鏈的開頭
            treeID[i]=j++;    //設為第j條鏈
            tree[treeID[i]].resize(len[i]*4,0);  //以線段樹為例
        }                                     //設第j條鏈的長度4倍大小
    }
}
 

void updatePath(int x,int y,int v){
    while(root[x]!=root[y]){        //若不在同一條鏈上
        if(depth[root[x]]>depth[root[y]]){      //優先更新深度深的鏈
            update(treeID[root[x]],0,dep[x]-dep[root[x]],v);
            x=father[root[x]];
        }
        else{
            update(treeID[root[y]],0,dep[y]-dep[root[y]],v);
            y=father[root[y]];
        }
    }
    int mn=min(dep[x],dep[y]),mx=max(dep[x],dep[y]);
    //更新第treeID[i]樹從mn~mx的範圍加值v
    update(treeID[root[x]],mn,mx,v);  //最後會連至同一條鏈上，更新範圍
}

由於剖分的性質，會使任一個點至根結點最多經過\(lgN\)條鏈，
每條鏈上的詢問、修改為\(O(lgN)\)

因此每筆詢問、修改為\(O(lgNlgN)\)
Q筆詢問則複雜度為\(O(QlgNlgN)\)

最多經過 \(lgN\) 條鏈，因此複雜度為 \(O(lgN)\)