题解 | #两棵树的问题#

思路：

题目的主要信息：

有两个结点数都为n，根都是1的树，设根的深度为0
定义点对(x,y)的价值为树1中x和y的最近公共祖先的深度+树2中a[x]和a[y]的最近公共祖先的深度
输出所有点对的最大值价值数组b与数组c分别记录树1与树2的各个节点的父节点

方法一：暴力解法（超时）
具体做法：
我们可以遍历树1的每一个点对，求得其在树1中得最近公共祖先深度，然后再用数组a转换后去求这两个点在树2中的公共祖先深度，二者相加，维护最大值。求LCA的时候，我们也是从这个节点依次往上遍历直到根，我们记录这其中的路径，然后从上往下最后一个相同的节点就是最近公共节点，记录其深度即可。

class Solution {
public:
    int LCA(int x, int y, vector<int>& z){ //暴力LCA，记录祖先路径再从上往下找最近的公共祖先
        if(x == 0)
            return 0;
        vector<int> path1; //记录节点x的路径
        vector<int> path2; //记录节点y的路径
        int temp = x;
        while(x != 0){ //x遍历祖先直到0
            if(z[x] != 0 && z[x] != y){
                x = z[x];
                path1.push_back(x);  //记录往上的路径
            }else if(z[x] == y)
                return 0;
            else if(z[x] == 0)
                break;
        }
        path1.push_back(0);
        while(y != 0){ //y遍历祖先直到0
            if(z[y] != 0 && z[y] != temp){
                y = z[y];
                path2.push_back(y); //记录往上的路径
            }else if(z[y] == temp)
                return 0;
            else if(z[y] == 0)
                break;
        }
        path2.push_back(0);
        int res = -1;
        int n = path1.size() - 1;
        int m = path2.size() - 1;
        while(n >= 0 && m >= 0 && path1[n] == path2[m]){ //从上往下找到第一个不同的祖先
            n--;
            m--;
            res++;
        }
        return res;
    }
    int wwork(int n, vector<int>& a, vector<int>& b, vector<int>& c) {
        int res = 0;
        for(int i = 1; i < n; i++){
            for(int j = i + 1; j <= n; j++){ //遍历每一个点对
                int temp = (LCA(i, j, b) + LCA(a[i], a[j], c)); //计算价值
                res = temp > res ? temp : res; //维护最大值
            }
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O(n^3)$ ，遍历所有点对，每个点对暴力求解LCA平均为 $O(log_2n)$ ，但是最坏情况可以到 $O(n)$
空间复杂度： $O(n)$ ，记录路径的辅助数组长度最长为 $n$ （退化为链表）

方法二：DFS + LCA
具体做法：
我们首先利用dfs遍历树2，找到节点的遍历次序，及从次序到到节点的关系，再记录树2每个节点的深度，然后记录树2祖先的祖先，为LCA倍增算法做预处理。用set维护树2的dfs次序建立虚树，利用dfs遍历树1枚举其每一个LCA，不断合并树2虚树的集合，其中set的lower_bound对应LCA最大的点，既可以找到我们所求的最大价值。
对于上述方法一求LCA的暴力算法，我们每次条一步，直到到根节点，但是对于倍增算法，我们对应的则是走1步、2步、4步……以此来倍增，通过dfs遍历，记录每个节点的次序及深度，并初始化求出树上每个节点u的 $2^i$ 祖先father[u][i]。求最近公共祖先时，根据两个节点的的深度，如不同，向上调整深度大的节点，使得两个节点在同一层上，如果正好是祖先结束，否则，将两个节点同时上移，查询最近公共祖先。（具体可以查看注释，注释很详细）
图片说明

class Solution {
public:
    vector<vector<int> > edge; //保存边
    vector<set<int>> Q;
    vector<vector<int>> father;
    vector<int> dfn, redfn, depth;
    int res = 0;
    int count = 0;
    void dfs1(int v, int deep){
        count++;
        dfn[v] = count; //dfs遍历次序
        redfn[count] = v; //由次序到节点
        depth[v] = deep; //记录树2某个节点的深度
        for(int i = 0; i < edge[v].size(); i++){
            dfs1(edge[v][i], deep + 1);
            father[edge[v][i]][0] = v; //记录父节点
        }
    }
    int LCA(int a, int b){ //倍增寻找最近公共祖先
        if(depth[a] < depth[b]) //a一定在下面
            swap(a, b);
        for(int i = 17; i >= 0; i--)
            if(depth[a] - depth[b] >= 1 << i) //找父亲节点
                a = father[a][i];
        if(a == b)
            return a;
        for(int i = 17; i >= 0; i--){
            if(father[a][i] != father[b][i]){   //从最大祖先开始，判断a,b祖先，是否相同
                a = father[a][i];  //如不相同，a b同时向上移动2^i
                b = father[b][i];
            }
        }
        return father[a][0];
    }
    int merge(set<int>& A, set<int>& B){ //合并AB集合
        if(A.size() < B.size())
            A.swap(B); //A为大集合，B为小集合
        int best = 0;
        for(int i: B){
            auto iter = A.lower_bound(i); //二分查找，找到A中第一个大于i的
            if(iter != A.end()) //找到
                best = max(best, depth[LCA(redfn[i], redfn[*iter])]);
            if(iter != A.begin()){ //不是第一个，向前缩
                iter--;
                best = max(best, depth[LCA(redfn[i], redfn[*iter])]);
            }
            A.insert(i);
        }
        B.clear();
        return best;
    }
    void dfs2(int v, int deep){ //遍历树1的节点
        int best = 0;
        for(int i = 0; i < edge[v].size(); i++){ 
            dfs2(edge[v][i], deep + 1);
            best = max(best, merge(Q[v], Q[edge[v][i]]));
        }
        res = max(res, best + deep); //最近的公共祖先加上本来的层
    }
    int wwork(int n, vector<int>& a, vector<int>& b, vector<int>& c) {
        edge.resize(n + 1);
        dfn.resize(n + 1, 0);
        redfn.resize(n + 1, 0);
        depth.resize(n + 1, 0);
        Q.resize(n + 1);
        father.resize(n + 1, vector<int>(18, 0)); //测试数据树最大深度不超过18
        for(int i = 2; i <= n; i++)
            edge[c[i]].push_back(i); //树2的父节点连接子节点的边
        dfs1(1, 0); // 对树2深度优先搜索记录其父节点
        for(int i = 1; i <= 17; i++) //初始化LCA
            for(int j = 1; j <= n; j++)
                father[j][i] = father[father[j][i - 1]][i - 1]; //往后依次是往上的祖先节点
        for(int i = 0; i <= n; i++)  //清空树2的边
            edge[i].clear();
        for(int i = 2; i <= n; i++)
            edge[b[i]].push_back(i); //树1的父节点连接子节点的边
        for(int i = 1; i <= n; i++)
            Q[i].insert(dfn[a[i]]); //树2对应节点进入集合
        dfs2(1, 0);
        return res;
    }
};

复杂度分析：

时间复杂度： $O(nlog(log_2n))$ ，主体函数循环都是 $O(n)$ ，两次dfs也都是 $O(n)$ ，合并函数为 $O(log_2n)$ ，LCA函数为 $O(log_2n)$
空间复杂度： $O(n)$ ，各个一维辅助数组的长度都为 $n+1$ ，二维的辅助数组第二维都是常数，故看成一维