关注
第二个换根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;
}
查看原帖
1 评论
相关推荐
07-18 20:15
浙江大学 算法工程师 点赞 评论 收藏
分享
06-02 23:35
门头沟学院 后端 
点赞 评论 收藏
分享
06-26 16:46
广东海洋大学 Java 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 第一份工作应该选高薪还是热爱? #
66669次浏览 592人参与
# 不考虑薪资和职业,你最想做什么工作呢? #
92039次浏览 678人参与
# 秋招签约后的心态变化 #
82486次浏览 813人参与
# 听劝,这个公司值得去吗 #
486024次浏览 1700人参与
# 你觉得早上几点上班合适? #
72305次浏览 303人参与
# 学历贬值真的很严重吗? #
24415次浏览 173人参与
# 机械人与华为的爱恨情仇 #
120136次浏览 957人参与
# 一人推荐一个值得去的通信/硬件公司 #
186457次浏览 1859人参与
# 打工人的工作餐日常 #
53155次浏览 415人参与
# 哪些公司真双非友好? #
15813次浏览 82人参与
# 26届的你们有几段实习? #
43832次浏览 486人参与
# 月薪多少能在一线城市生存 #
27725次浏览 303人参与
# 双非能在秋招上岸吗? #
221695次浏览 1172人参与
# 你以为的实习VS真实的实习 #
29528次浏览 272人参与
# 今年秋招哪家公司给的薪资最良心? #
252829次浏览 1417人参与
# 你后悔自己读研吗? #
20463次浏览 240人参与
# 当下环境,你会继续卷互联网,还是看其他行业机会 #
117881次浏览 812人参与
# 追觅科技求职进展汇总 #
18221次浏览 120人参与
# 实习想申请秋招offer,能不能argue薪资 #
149865次浏览 932人参与
# 如何KTV领导 #
62765次浏览 472人参与