龍龍是“飽了呀”外賣軟件的注冊騎手，負責送帕特小區的外賣。帕特小區的構造非常特別，都是雙向道路且沒有構成環 —— 你可以簡單地認為小區的路構成了一棵樹，根結點是外賣站，樹上的結點就是要送餐的地址。

每到中午 12 點，帕特小區就進入了點餐高峰。一開始，只有一兩個地方點外賣，龍龍簡單就送好了；但隨著大數據的分析，龍龍被派了更多的單子，也就送得越來越累……

看著一大堆訂單，龍龍想知道，從外賣站出發，訪問所有點了外賣的地方至少一次（這樣才能把外賣送到）所需的最短路程的距離到底是多少？每次新增一個點外賣的地址，他就想估算一遍整體工作量，這樣他就可以搞明白新增一個地址給他帶來了多少負擔。

輸入格式:

輸入第一行是兩個數 N 和 M (2≤N≤105, 1≤M≤105)，分別對應樹上節點的個數（包括外賣站），以及新增的送餐地址的個數。

接下來首先是一行 N 個數，第 i 個數表示第 i 個點的雙親節點的編號。節點編號從 1 到 N，外賣站的雙親編號定義為 ?1。

接下來有 M 行，每行給出一個新增的送餐地點的編號 Xi?。保證送餐地點中不會有外賣站，但地點有可能會重復。

為了方便計算，我們可以假設龍龍一開始一個地址的外賣都不用送，兩個相鄰的地點之間的路徑長度統一設為 1，且從外賣站出發可以訪問到所有地點。

注意：所有送餐地址可以按任意順序訪問，且完成送餐后無需返回外賣站。

輸出格式:

對于每個新增的地點，在一行內輸出題目需要求的最短路程的距離。

輸入樣例:

7 4
-1 1 1 1 2 2 3
5
6
2
4

輸出樣例:

2
4
4
6

#include<bits/stdc++.h>
using namespace std;
vector<int>tree;
vector<int>children[100005];
int path[100005]={0};
bool vis[100005]={false};
void dfs(int root){queue<pair<int,int>>pq;pq.push({root,path[root]});while(!pq.empty()){int pa=pq.front().first;int deep=pq.front().second;pq.pop();path[pa]=deep;for(int u:children[pa]){pq.push({u,deep+1});}}
}
void solve(){int n,m;cin>>n>>m;tree.resize(n+1);int root;for(int i=1;i<=n;i++){cin>>tree[i];if(tree[i]==-1){root=i;}else{children[tree[i]].push_back(i);}}dfs(root);set<int>address;int total=0;int maxn=0;for(int i=0;i<m;i++){int q;cin>>q;maxn=max(path[q],maxn);while(q!=root&&!vis[q]){vis[q]=true;total++;q=tree[q];}cout<<total*2-maxn<<endl;}
}
int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);solve();return 0;
}

?