题意分析

  • 给出一个以1为根的树，然后是m个询问，对于每个询问，需要我们计算从结点1到这个被询问的结点的最大的花费是多少？（题目中说的是至少要带多少金币才可以保证任何情况下都可以找到牛妹，所以应该是一个最大的花费。）

思路分析

  • 首先，我们观察题目，我们发现这个题目是一个多组询问，所以应该是需要先进行一个预处理。然后我们通过画图可以观察得到为了考虑到最坏的情况。牛牛一定是先走无关的分岔口，然后就是一步一步的逼近这个点。而且，对于被询问的点的后面的一些路径，这些路径是一定没有必要通过的。然后，对于一棵普通的树，如果我们想要遍历所有的结点，最坏的情况就是每条路径走两遍。但是这个题目有一个限制，就是牛牛走了的边，如果存在没有走的边，那么牛牛会先考虑没有走的边。根据画图可以观察到，从根节点到牛妹所在的点的路径只需要走一遍，牛妹之后的路径一遍也没有必要走。其他路径一定要走两遍就是每个询问的答案了。

  • 整理一下，也就是我们需要先预处理出树上的每个点到根节点的路径的长度，然后预处理出每个结点的子节点的个数。最后就可以直接得出每个询问的答案啦。

  • 请结合下面的图进行理解

图片说明

  • 知道了思路，我们就可以像办法求解了。首先，我们利用树形DP求得我们每个结点到根节点的路径长度和这个结点的子节点的个数。然后直接O(1)求解即可。

写法一 C++版

  • 代码如下
    • 树形最坏的时间是遍历条边.每次询问的时间复杂度为,所以总的时间复杂度为.
    • 我们需要存储条边和个结点的相关信息，所以空间复杂度为. 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param m int整型 
     * @param u int整型vector 
     * @param v int整型vector 
     * @param x int整型vector 
     * @return int整型vector
     */
    vector<int> node[200010];
    int dep[200010],son[200010];
    // 树形DP预处理出每个结点的子节点的个数和到根节点的距离
    void dp(int x,int fa){
        son[x]=0;
        for(auto y:node[x]){
            if(y==fa) continue;
            dep[y]=dep[x]+1;  // 深度为父节点的深度+1
            son[x]++;  // 儿子的个数+1
            dp(y,x); // 先处理儿子的情况
            son[x]+=son[y];  // 累加儿子的子节点
        }
    }
    vector<int> solve(int n, int m, vector<int>& u, vector<int>& v, vector<int>& x) {
        // write code here
        // 所有的路的条数的两倍-从1号结点到这个位置的的路径长度-这个结点的后面的所有的路径的两倍
        for(int i=0;i<n-1;i++){
            node[u[i]].push_back(v[i]);
            node[v[i]].push_back(u[i]);
        }

        dep[1]=0;
        dp(1,0);

        vector<int> ans;
        int sum=(n-1)*2;
        for(auto pos:x){
            // 当前询问的答案就是减去到根节点的距离和这个子树的边的条数的两倍
            int tmp=sum-dep[pos]-son[pos]*2;
            ans.push_back(tmp);
        }
        return ans;
    }

};

写法二 Go语言版

  • 为Go社区贡献自己的一份力量。思路其实和上面的一样。而且本题的解法有限，所以写一发Go版本的吧。不过这里我存储这个树使用的二维切片进行存储的，所以在判断连边的时候需要遍历所有的结点。据我所知go里面好像没有类似于C++的STL这样方便的东西。

  • 代码如下

    • 树形最坏的时间是遍历个结点。但是每个结点判断连边的时候又是。每次询问的时间复杂度为,所以总的时间复杂度为.
    • 这里用的二维切片存储的这个树，所以空间复杂度为. 
package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @param m int整型 
 * @param u int整型一维数组 
 * @param v int整型一维数组 
 * @param x int整型一维数组 
 * @return int整型一维数组
*/
func dp(x int,fa int,n int,matrix [][]int, dep []int, son []int){
    son[x]=0;
    // 注意这里用的是二维矩阵进行存储
    for i:=1; i<=n; i++ {
        if(matrix[x][i]==1){
            if(i==fa){
                continue;
            }
            dep[i]=dep[x]+1
            son[x]++
            // 继续向下递归
            dp(i,x,n,matrix,dep,son)
            son[x]+=son[i];
        }
    }
}
func solve( n int ,  m int ,  u []int ,  v []int ,  x []int ) []int {
    // write code here
    // 进行一系列的初始化的操作
    matrix := make([][]int,n+10)
    dep := make([]int,n+10)
    son := make([]int,n+10)
    for i:=0; i<len(matrix); i++ {
        matrix[i]=make([]int,n+10)
    }


    // 存储连边情况
    for i := range u {
        matrix[u[i]][v[i]]=1
        matrix[v[i]][u[i]]=1
    }

    dep[1]=0

    dp(1,0,n,matrix,dep,son)

    // 这里我们先把切片的容量初始化为0，因为后面append的时候会动态进行扩展
    var ans = make([]int,0)
    sum := 2*(n-1)
    for i := range x {
        ans=append(ans,sum-dep[x[i]]-son[x[i]]*2)
    }
    return ans;
}