每到中午 12 点,帕特小区就进入了点餐高峰。一开始,只有一两个地方点外卖,龙龙简单就送好了;但随着大数据的分析,龙龙被派了更多的单子,也就送得越来越累……
接下来首先是一行 N 个数,第 i 个数表示第 i 个点的双亲节点的编号。节点编号从 1 到 N,外卖站的双亲编号定义为 −1。
接下来有 M 行,每行给出一个新增的送餐地点的编号 Xi。保证送餐地点中不会有外卖站,但地点有可能会重复。
做法:
为了维护节点的最大深度,我们先预处理所有节点的深度,一次dfs就能完成。然后我们依次遍历题目中给出的m个点,从这m个点向上找根节点或者之前访问过的节点。这样计算的第一种情况的答案,之后根据每一个新增节点更新最大深度减去即可。因为每一个点仅仅遍历一次,时间复杂度在O(n)。
不过如果你对给出双亲结点建树的这类题不熟悉,你应该会卡在第一步,应该注意这种情况不能使用dfs暴力求解,因为这样很难标记路过的节点(题主也是卡在了这一步...)。我们看到题目中给出了每一个节点的双亲结点,所以直接考虑不断使用其双亲结点来向上找。
我的代码:
#include<iostream>
#include<cstring>
using namespace std;
const int N = 2e5+5;
int h[N],ne[N],e[N],idx,vis[N],d[N],maxn,root,f[N];
void add(int u,int v){
e[idx] = v;
ne[idx] = h[u];
h[u] = idx++;
}
void dfs(int u,int dep){
d[u] = dep;
for(int i = h[u]; ~i; i = ne[i]){
int v = e[i];
if(d[v] == 0) dfs(v,d[u]+1);
}
}
int main(){
int n,m;
cin >> n >> m;
memset(h,-1,sizeof h);
for(int i = 1; i <= n; i++){
cin >> f[i];
if(f[i] == -1) root = i;
else add(f[i],i);
}
dfs(root,0);
int v = 0,maxn = 0;
for(int i = 1; i <= m; i++){
int x;
cin >> x;
maxn = max(maxn,d[x]);
for(;!vis[x] && x!=root; x = f[x]){
vis[x] = 1,v += 2;
}
cout << v-maxn << endl;
}
return 0;
}
因篇幅问题不能全部显示,请点此查看更多更全内容
怀疑对方AI换脸可以让对方摁鼻子 真人摁下去鼻子会变形
女子野生动物园下车狼悄悄靠近 后车司机按喇叭提醒
睡前玩8分钟手机身体兴奋1小时 还可能让你“变丑”
惊蛰为啥吃梨?倒春寒来不来就看惊蛰
男子高速犯困开智能驾驶出事故 60万刚买的奔驰严重损毁