2023-09-28 20:40 辽宁工程技术大学 算法工程师
关注
滴滴笔试
1好的三元组，回溯+dfs，不知道怎么去回溯
2树的结点到其他结点的距离的总和，应该是强连通分量下的bfs吗？
2树的结点到其他结点的距离的总和，应该是强连通分量下的bfs吗？
全部评论
牛客502675548号
西安电子科技大学 算法工程师
第二题是换根dp，力扣第834题
aihuaxinhuadenghua
门头沟学院 Java
dfs 36%，一直超时，优化不出来
憕
门头沟学院 C++
第二个换根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;
}
Handa_Rei
华南理工大学 C++
第一题回溯加记忆化搜索，避免重复计算，可以ac。第二题暴力过了73%，感觉可以打表，但不会打
Demo_d
门头沟学院 前端工程师
输出2*n，偷了18%
无畏丶无惧
华中科技大学 Java
dd还有hc么
牛客720291255号
门头沟学院 Java
1.算出所有节点子树上节点的数量nums和子树的所有距离zdis
2.然后根节点子树所有距离就是距离整个树的距离，通过nums，zdis，以及父节点的整个树所有点距离，来递归向下计算当前节点的整个树的距离
想逆袭好楠
领星网络_星拓_后台开发
我两个题都是直接输出了案例，然后都是百分之18
sunnywizard
门头沟学院 Java
第二题BFS
相关推荐
点赞 评论 收藏
分享
查看11道真题和解析