第二个换根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; }

相关推荐

门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
程序员小白条:找的太晚,别人都是大三实习,然后大四秋招春招的,你大四下了才去实习,晚1年
点赞 评论 收藏
分享
牛客网
牛客网在线编程
牛客网题解
牛客企业服务