滴滴笔试

第二题是换根dp，力扣第834题

dfs 36%，一直超时，优化不出来

输出2*n，偷了18%

第一题回溯加记忆化搜索，避免重复计算，可以ac。第二题暴力过了73%，感觉可以打表，但不会打

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

第二题BFS

我两个题都是直接输出了案例，然后都是百分之18

1.算出所有节点子树上节点的数量nums和子树的所有距离zdis 2.然后根节点子树所有距离就是距离整个树的距离，通过nums，zdis，以及父节点的整个树所有点距离，来递归向下计算当前节点的整个树的距离

dd还有hc么