例一：力扣310：最小高度树

求以每个节点为根时，树的高度。首先可以通过dfs求出树的高度，时间复杂度$O(n)$但如果每个节点都作为根dfs一遍，时间复杂度是$O(n^2)$。通过换根的思想可以做到只需要进行两次dfs就得出答案，在以任意一个节点（如0号节点）进行一遍dfs后，我们已经有dep数组，dep[i]表示以i节点为根的子树的高度。这时再对同一个节点（0号节点）进行一遍dfs，这次的dfs和上一次不同，这次在dfs的过程中进行换根的操作，第一次换根如图，把0的子节点1作为根节点，这时可以发现只有dep[0]和dep[1]发生改变，并且改变后的数值也可以求出来，这样就能求出以1号节点为根的树高。接着dfs下去就可以求出所有答案，详见dfs2函数

int *h, *res, *ans, *e, *ne, *dep;
int max(int a, int b){
    return a > b ? a : b;
}
int min(int a, int b){
    return a < b ? a : b;
}
void add(int a, int b, int *idx){
    e[*idx] = b;
    ne[*idx] = h[a];
    h[a] = (*idx)++;
}
void dfs1(int cur, int fa){
    dep[cur] = 1;
    for(int i = h[cur]; ~i; i = ne[i]){
        int ch = e[i];
        if(ch != fa){
            dfs1(ch, cur);
            dep[cur] = max(dep[cur], dep[ch] + 1);  
        }
    }
}
void dfs2(int cur, int fa){
    res[cur] = dep[cur];
    for(int i = h[cur]; ~i; i = ne[i]){
        int ch = e[i];
        if(ch != fa){
            int depcur = dep[cur], depch = dep[ch];
            if(dep[cur] == dep[ch] + 1){
                dep[cur] = 1;
                for(int i = h[cur]; ~i; i = ne[i]){
                    int ch2 = e[i];
                    if(ch2 != ch){
                        dep[cur] = max(dep[cur], dep[ch2] + 1);
                    }
                }
            }
            dep[ch] = max(dep[ch], dep[cur] + 1);
            dfs2(ch, cur);
            dep[cur] = depcur, dep[ch] = depch;
        }
    }
}
int* findMinHeightTrees(int n, int** edges, int edgesSize, int* edgesColSize, int* returnSize) {
    int idx = 0;
    h = (int *)malloc(sizeof(int) * n);
    e = (int *)malloc(sizeof(int) * (edgesSize * 2 + 5));
    ne = (int *)malloc(sizeof(int) * (edgesSize * 2 + 5));
    dep = (int *)malloc(sizeof(int) * n);
    res = (int *)malloc(sizeof(int) * n);
    ans = (int *)malloc(sizeof(int) * n);
    int retSize = 0;
    for(int i = 0; i < n; i++)h[i] = -1, dep[i] = 0;
    for(int i = 0; i < edgesSize; i++){
        int a = edges[i][0], b = edges[i][1];
        add(a, b, &idx);
        add(b, a, &idx);
    }
    dfs1(0, -1);
    dfs2(0, -1);
    int mn = INT_MAX;
    for(int i = 0; i < n; i++)mn = min(mn, res[i]);
    for(int i = 0; i < n; i++){
        if(res[i] == mn){
            ans[retSize++] = i;
        }
    }
    *returnSize = retSize;
    return ans;
}

例二：力扣834：树中距离之和

与上一题思路相同，首先定义dp数组和sz数组，dp[i]表示i节点为根时，其所有子节点到它的距离和，sz[i]表示以i为根的子树的大小，dfs回溯的过程中，可以求出根节点在answer数组中的值

但现在只求出了一个节点的答案，我们可以进行换根dp，每次父节点减去要换成根的子节点的贡献得到换根后父节点的dp值，再更新换成根的子节点的dp值，就是这个子节点的答案。

void add(int a, int b, int *h, int *e, int *ne, int *idx){
    e[*idx] = b;
    ne[*idx] = h[a];
    h[a] = (*idx)++;
}
void dfs(int p, int f, int *dp, int *sz, int *h, int *e, int *ne){
    sz[p] = 1;
    dp[p] = 0;
    if(h[p] == -1)return;
    for(int i = h[p]; ~i; i = ne[i]){
        int ch = e[i];
        if(ch != f){
            dfs(ch, p, dp, sz, h, e, ne);
            dp[p] += dp[ch] + sz[ch];
            sz[p] += sz[ch];
        }
    }
}
void dfs2(int p, int f, int *ans, int *dp, int *sz, int *h, int *e, int *ne){
    ans[p] = dp[p];
    for(int i = h[p]; ~i; i = ne[i]){
        int ch = e[i];
        if(ch != f){
            int dpp = dp[p], szp = sz[p], dpch = dp[ch], szch = sz[ch];
            dp[p] -= dp[ch] + sz[ch];
            sz[p] -= sz[ch];
            dp[ch] += dp[p] + sz[p];
            sz[ch] += sz[p];
            dfs2(ch, p, ans, dp, sz, h, e, ne);
            dp[p] = dpp, sz[p] = szp, dp[ch] = dpch, sz[ch] = szch;
        }
    }
}
int* sumOfDistancesInTree(int n, int** edges, int edgesSize, int* edgesColSize, int* returnSize) {
    int h[n], e[edgesSize * 2 + 5], ne[edgesSize * 2 + 5], idx;
    int dp[n], sz[n];
    int *ans = (int *)malloc(sizeof(int) * n);
    for(int i = 0; i < n; i++)h[i] = -1;
    for(int i = 0; i < edgesSize; i++){
        int a = edges[i][0], b = edges[i][1];
        add(a, b, h, e, ne, &idx);
        add(b, a, h, e, ne, &idx);
    }
    dfs(0, -1, dp, sz, h, e, ne);
    dfs2(0, -1, ans, dp, sz, h, e, ne);
    *returnSize = n;
    return ans;
}