开学二周（日常补题训练）

whatdo / 2024-03-13 / 原文

pta天梯专栏

7-11 龙龙送外卖 - SMU 2024 spring 天梯赛1(补题) (pintia.cn)

题解:首先我们先建个图然后存一下各个节点的父亲节点

我们细看这个最短路可以发现，当全部节点加进来，那么最短路就是每一个节点跑两遍然后最深的那个节点最后才跑，这样就只需要1遍

所以我们首先把每一个节点的深度算出来，然后分别记录

然后我们一个个把需要用到的点加进来，从这个节点向上跑到根节点或者跑到之前跑过的点记录答案即可，

如果这点跑过，直接输出答案即可ans-ma+1

ma是最大的深度

#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
//#define double long double
#define int long long
#define endl '\n'
using namespace std;
const int N=1e5+9,M=1e1;
const int INF = 0x3f3f3f3f;
const int mod=1e9+7;
typedef pair<int,int> PII;
int kmp(int a,int k,int p)
{
    int ans=1;
    while (k)
    {
        if(k&1) ans=ans*a%p;
        k>>=1;
        a=a*a;
    }
    return ans;
}

vector<int> a[N];
int fa[N];
int dep[N];
bool st[N];
int ans;
int root=0;
void dfs1(int u,int de)
{
    dep[u]=de;
    for(auto i:a[u])
    {
        dfs1(i,de+1);
    }
}
void dfs2(int u)
{
    if(st[u] || u==root) return;
    st[u]= true;
    ans+=2;
    dfs2(fa[u]);
}
void solve()
{
    int n,m;
    cin>>n>>m;

    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        if(x==-1)
        {
            root=i;
            fa[i]=i;
        }
        else
        {
            a[x].push_back(i);
            fa[i]=x;
        }
    }
    dfs1(root,1);
    int ma=-1;
    while (m--)
    {
        int x;
        cin>>x;
        if(st[x]) cout<<ans-ma+1<<endl;
        else
        {
            ma=max(ma,dep[x]);
            dfs2(x);
            cout<<ans-ma+1<<endl;
        }
    }
}
signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T=1;
//    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}