关于树

树的直径

树的直径是指树中两个点之间的最大距离，即最长的一条链。

容易证明(~~信奥不需要证明~~)，树的直径的起始点是该树的叶子节点。

求树的直径一般有两种方法，一种是两遍\(dfs\)，另一种是树形\(DP\)。

两遍dfs

我们随便从一个点\(u\)出发，然后去寻找一个离这个点最远的一个点\(v\)。

然后再从这个点v出发去寻找最长链。

void dfs(int x,int p) {
    for(re int i = head[x] ; i ; i = t[i].next) {
        int v = t[i].to;
        if(vis[v]) continue;
        vis[v]=1;
        dis[v] = p + t[i].dis;
        if(dis[v] > ans) {
            ans=dis[v];
            node=v;
        }
        dfs(v,dis[v]);
    }
}

树形DP

用\(f[x][1]\)维护在x的子树中的最长链。

用\(f[x][2]\)维护在x的子树中的次长链。

那么在\(x\)的子树中的最长链就是\(f[x][1]+f[x][2]\).

void dfs(int x, int fa) {
    for(re int i = head[x]; i; i = t[i].net) {
        int v = t[i].to;
        if(v == fa) continue; dfs(v,x);
        if(l[v][1] + t[i].dis > l[x][1])
            l[x][2] = l[x][1], l[x][1] = l[v][1] + t[i].dis;
        else if(l[v][1] + t[i].dis > l[x][2])
            l[x][2] = l[v][1] + t[i].dis;
        if(lian < l[x][1]+l[x][2]) lian = l[x][1] + l[x][2];
    }
}

树上求LCA

LCA(Lowest Common Ancestors)即最近公共祖先，

是指在有根树中，找出某两个结点\(u\)和\(v\)最近的公共祖先.

目前只会两种方法，倍增和树链剖分。

倍增求LCA

f[x][i]是指节点x向上第\(2^i\)个节点。

有一个关键的式子：\(f[x][i]=f[f[x][i-1]][i-1].\)

void dfs(int x, int fa) {
    f[x][0] = fa; deep[x] = deep[fa] + 1;
    for(re int i = 1; (1 << i) <= deep[x]; ++ i) //不超过根节点
        f[x][i] = f[f[x][i-1]][i-1];
    for(re int i = head[x]; i; i = t[i].net)
        if(t[i].to != fa) dfs(t[i].to, x);
}
int lca(int x, int y) {
    if(deep[x] < deep[y]) std :: swap(x,y); // 让x为深度更大的
    for(re int i = 21; i >= 0; -- i)
        if(deep[x] - (1 << i) >= deep[y]) // 使x的深度始终大于或等于y
            x = f[x][i];
    if(x == y) return x;
    for(re int i = 21; i >= 0; -- i)
        if(f[x][i] == f[y][i]) continue;
        else x = f[x][i], y = f[y][i];
    return f[x][0]; // x的父亲一定是LCA
}

树链剖分求LCA

每一个节点都去维护一个子树大小，深度，链顶，父亲，最重链(最大子树)。

第一次\(dfs\)去求深度，父亲和子树大小。

第二次\(dfs\)去求链顶。

求\(LCA\)的时候，不断的更新链顶深度大的，使其在同一深度。

\(LCA\)就是深度小的那个。

void dfs_1(int x) {
    deep[x] = deep[fa[x]] + 1; size[x] = 1;
    for(re int i = head[x]; i; i = t[i].net) {
        int v = t[i].to;
        if(fa[x] == v) continue; // 父亲已经遍历了
        fa[v] = x; dfs_1(v);
        size[x] += size[v];
        if(size[son[x]] < size[v] || !son[x]) son[x] = v;
        //没有儿子或者是儿子的子树重量没有当前子树重量大，都会更新
    }
}
void dfs_2(int x, int tp) {
    top[x] = tp; // 一条链上的人链顶都相同
    if(son[x]) dfs_2(son[x],tp); // 还有儿子
    for(re int i = head[x]; i; i = t[i].net) {
        int v = t[i].to;
        if(fa[x] == v || son[x] == v) continue;
        // 父亲和儿子都遍历过了
        dfs_2(v, v);
    }
}
int lca(int x, int y) {
    while(top[x] != top[y]) { // 更新深度大的
        if(deep[top[x]] < deep[top[y]]) y = fa[top[y]];
        else x = fa[top[x]];
    }
    return deep[x] < deep[y] ? x : y;
}