寻找牛妹

最优题解

容易发现这是一棵树，1为根。那么走到牛妹所在的x的最大花费相当于x的子树中的通道都不走，x到根节点的通道只走一次，其他通道全走两次。用sz[x]表示x子树中通道数量,dep[x]表示根到x的通道数量，那么对于特定的x，答案就是2n-2-2sz[x]-dep[x]
时间复杂度和空间复杂度都是

vector<int> g[200055];
int sz[200055], dep[200055];
void dfs(int u, int f){
    sz[u] = 0; dep[u] = dep[f] + 1;
    for(int v: g[u]) if(v!=f) dfs(v, u), sz[u] += sz[v]+1;
    return;
}
vector<int> solve(int n, int m, vector<int> &u, vector<int>&v, vector<int> &x){
    for(int i = 0; i <= n; ++i)
        g[i].clear(), dep[i] = sz[i] = 0;
    assert(u.size() == n-1 && v.size() == n-1 && x.size() == m );
    for(int i = 0; i < n-1; ++i){
        g[u[i]].push_back(v[i]);
        g[v[i]].push_back(u[i]);
    }
    dep[0] = -1;
    dfs(1, 0);
    vector<int>ans;ans.clear();
    for(int i = 0; i < m; ++i){
        ans.push_back(2*n-2-2*sz[x[i]]-dep[x[i]]);
    }return ans;
}