第二个换根dp
A的代码：#include<bits/stdc++.h>
(35927)#define int long long
using namespace std;
const int N = 1e5+5;
struct Node{
int u,v,next;
}a[N];
int n,m;
int tot,last[N];
int ans[N];
int dp[N];
int sum[N];
void add(int u,int v)
{
tot++;
a[tot].u = u;
a[tot].v = v;
a[tot].next = last[u];
last[u] = tot;
}
void dfs(int u,int fa)
{
for(int i = last[u];i >= 0;i = a[i].next)
{
int v = a[i].v;
if(v == fa)
{
continue;
}
dfs(v,u);
sum[u] += sum[v] + 1;
dp[u] += dp[v] + sum[v]+1;
}
}
void dfs2(int u,int fa)
{
for(int i = last[u]; i >= 0; i = a[i].next)
{
int v = a[i].v;
if(v == fa)
{
continue;
}
ans[v] = dp[v] + (ans[u] - (dp[v] + sum[v] + 1 )) + ( n - sum[v] - 1);
dfs2(v,u);
}
}
signed main()
{
tot = -1;
memset(last,-1,sizeof(last));
cin>>n>>m;
for(int i = 2;i <= n; i++)
{
int u,v;
cin>>u;
add(i,u);
add(u,i);
}
memset(dp,0,sizeof(dp));
dfs(1,-1);
ans[1] = dp[1];
dfs2(1,-1);
for(int i = 1;i <= m; i++)
{
int u;
cin>>u;
cout<<ans[u];
if(i == m)
{
cout<<endl;
}
else{
cout<<" ";
}
}
return 0;
}
