题解 | #小红的陡峭值（四）#

简单些的暴力想法就是建好树以后直接从一个节点遍历一遍并且记录好方向，同时算出总的陡峭峰值，然后暴力从每个点按照这个方向遍历一遍树用数组记录好每个点为根节点的树的陡峭峰值，同时记录好自己的父亲，最后计算出总峰值减去两倍子峰值减去这个点加父亲的权值。但是这样的时间复杂度是n²，无法通过此题。我们可以在遍历的时候记录父亲到儿子的权值所有权值并且全部累加到父亲上，最后再从最大的深度往上走，累加回去就可以直接求出每个点的深度，这样的时间复杂度就是On，可以通过此题目。

```#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
using ll=long long;
vector<int>v[N];
vector<int>vx[N];//每个深度上的点
int vs[N];//记录深度
int p[N];
queue<int>q;
ll ans=1e18;
ll dp[N];//记录这个节点的权值
int dep;//最大深度
int main(){
    int n;cin>>n;
    for(int i=1;i<n;i++){
        int x,y;cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    q.push(1);
    vs[1]=1;
    while(q.size()){
        int x=q.front();
        q.pop();
        int mm=v[x].size();
        for(int i=0;i<mm;i++){
            int zz=v[x][i];
            if(vs[zz]!=0)continue;
            vs[zz]=vs[x]+1;
            dep=max(dep,vs[zz]);
            vx[vs[zz]].push_back(zz);
            q.push(zz);
            dp[x]+=abs(x-zz);
            p[zz]=x;
        }
    }
    for(int i=dep;i>=2;i--){
        for(int j=0;j<vx[i].size();j++){
            int zz=vx[i][j];
            int yy=p[zz];
            dp[yy]+=dp[zz];
        }
    }
    for(int i=2;i<=n;i++){
        ans=min(ans,abs(dp[1]-dp[i]-dp[i]-abs(i-p[i])));
    }
    cout<<ans;
    return 0;
}