# 樹直徑 & 樹重心

## APCS Judge
https://judge.apcs.camp/
帳號：lyp
密碼：Apcs510562

## 樹直徑

* 通常是指無根樹
* 距離最遠的兩個點就是樹直徑的兩端

### Naive
暴力窮舉倆倆端點$O(N^2)$，計算其距離$O(N)$，總共$O(N^3)$。

### O(N) solution
1. 分叉一定比較短
2. 無論哪個點開始走，其最遠的節點一定是樹直徑兩端的其中一端 O(N)
3. 既然找到其中一端，就從該點出發，找最遠的，即是另一端 O(N)

const int N = 10000;
// 1 ~ N
vector<int> graph[N+5];

int maxDepth;

void dfs(int current, int parent, int depth, int* endPoint) {
    if (depth > maxDepth) {
        *endPoint = current;
        maxDepth = depth;
    }
    // for (int next: graph[current]) {
    for (int i=0; i<graph[current].size(); i++) {
        int next = graph[current][i];
        if (next != parent) {
            dfs(next, current, depth+1);
        }
    }
}

void findDiameter() {
    // randomly pick one node to start, let's say node 1.
    
    int endPoint1, endPoint2;
    maxDepth = 0;
    dfs(1, -1, 0, &endPoint1);
    
    maxDepth = 0;
    dfs(endPoint1, -1, 0, &endPoint2);
    
    cout << endPoint1 << " " << endPoint2 << " " << maxDepth << endl;
}

## 樹重心

假設有Ｎ個點，把樹重心拿掉之後，最大的那棵子樹的大小不超過$\frac{N}{2}$。

最多只有兩個重心，證明見下圖。

## 二分圖 Bipartite graph

vector<int> graph[100005];
int c[100005]; // initialized with -1

bool dfs(int index, int color/* 0, 1*/) {
    c[index] = color;
    for(auto adj: graph[index]) {
        if (c[adj] == -1) {
            if(!dfs(adj, 1-color)) {
                return false;
            }
        }
        else if (c[adj] == color) {
            return false;
        }
    }
    return true;
}


dfs(1, 0);

## Some Practices Related to Trees
(不一定跟直徑跟重心直接相關)
#### APCS 2020
https://zerojudge.tw/ShowProblem?problemid=f163
https://judge.apcs.camp/problems/125

struct node {
    int index, weight_sum;
    int left_child, right_child;
};

node tree[2000005] ;

void dfs(int index) {
    // Ending criteria.
    if (tree[index].left_child == -1 && ) {
        tree[index].weight_sum = box[index];
        return;
    }
    // Not every node has l and r.
    int l = tree[index].left_child;
    int r = tree[index].right_child;
    dfs(l);
    dfs(r);
    tree[index].weight_sum += (tree[l].weight_sum + tree[r].weight_sum);
    return;
}

#### AtCoder 148F
https://atcoder.jp/contests/abc148/tasks/abc148_f
https://judge.apcs.camp/problems/146