**

题意：龙龙送外卖的小区构成了一棵树，外卖站为根节点。每次新增一个点外卖的地址，从外卖站出发，求出访问了所有点了外卖的地方至少一次（这样才能把外卖送到）所需的最短路程的距离.一开始一个地址的外卖都不用送，两个相邻的地点之间的路径长度统一设为 1，且从外卖站出发可以访问到所有地点。

题解： 主要看你能不能找到关键点，即最短路程 等于 经过边的路程 * 2 - 最深点的度数。然后更新添加一个点时经过边的路程和最深点的度数。

代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e5+10;
vector<vector<int>> c;//相当于邻接矩阵
bool st[N];//判断点是否添加过
int ma;//路程
int d;//最大深度
int dist[N];//度数
int f[N];//父节点
int bg = 0;//外卖站

void dfs(int u,int len)
{
    dist[u] = len;
    for(auto it : c[u])
    {
        dfs(it,len+1);
    }
}

void dfs2(int u)
{
    if(st[u]  || u==bg)return;
    st[u]=true;
    ma+=2;
    dfs2(f[u]);
}


int main()
{
    int n,m;
    cin>>n>>m;
    c.resize(n+1);//比邻接矩阵方便多了 必须要开辟空间
    for(int i=1;i<=n;i++)
    {
        int t;cin>>t;
        if(t!=-1){
            c[t].push_back(i);
            f[i] = t;
        }else bg = i,f[i]=i;
    }
    dfs(bg,0);
    
    while(m--)
    {
        int t;cin>>t;
        if(st[t])cout<<ma-d<<endl;
        else{
            d = max(d,dist[t]);
            dfs2(t);
            cout<<ma-d<<endl;
        }
        
    }
    
}