Codeforces-Gym102346—D.Denouncing Mafia

codeforces
题意：好像是给你一些一棵树，然后让你删最长链，删m次，问你累计ans最多多少
解题思路：主要是记录每个父节点最长链延申的最远儿子节点在哪里，这是一个需要注意的点，然后每次删完这个链，利用最远儿子向上标记，维护一个优先队列就够了，标记过的点直接跳过。

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int maxn=1e5+9;
int p[maxn];
priority_queue<pair<int,int> >q;
vector<int>v[maxn];
int book[maxn];
int fa[maxn];
int dp[maxn];
int pos[maxn];
void dfs(int x)
{
    int f=0;
// cout<<dp[x]<<endl;
    for(int i=0; i<v[x].size(); i++)
    {
        f=1;
        int y=v[x][i];
        dfs(y);
// dp[x]=max(dp[y]+1,dp[x]);
        if(dp[y]+1>dp[x])
        {
            dp[x]=dp[y]+1;
            pos[x]=pos[y];
        }
    }
    if(!f)
    {
        dp[x]=1;
        pos[x]=x;
// cout<<"dp[x]="<<x<<" "<<dp[x]<<endl;
    }
}
void findx(int x)
{
    if(fa[x]==x)
    {
        book[x]=1;
        return;
    }
    if(book[x])return;
    book[x]=1;
    findx(fa[x]);
    return;
}

int main()
{

    cin>>n>>m;
    fa[1]=1;
    for(int i=2; i<=n; i++)
    {
        scanf("%d",&p[i]);
        v[p[i]].push_back(i);
        fa[i]=p[i];
    }
    dfs(1);
    for(int i=1; i<=n; i++)
    {
        q.push(make_pair(dp[i],i));
    }
    int ans=0;
// for(int i=1; i<=n; i++)
// cout<<i<<" "<<dp[i]<<" "<<endl;
    while(q.size())
    {
        int y=q.top().second;
        if(book[y])
        {
            q.pop();
            continue;
        }
        if(m)
        {
// cout<<q.top().first<<" "<<q.top().second<<endl;
            book[y]=1;
            ans+=q.top().first;
            q.pop();
            m--;
            findx(pos[y]);
        }
        else
        {
            break;
        }
    }
// for(int i=1;i<=n;i++)
// cout<<"book=="<<book[i]<<" "<<pos[i]<<endl;
    cout<<ans<<endl;
}

小结一下，哎，今天虽然刚刚写了两篇博客，但是还是没有写难度更高的那些内容，像昨天训练赛的artwork就没有好好补一补，并查集维护各个联通块，这个需要好好补补，另外的话，算法竞赛进阶指南要推进鸭！希望明天也要元气满满，好好补题，哎对，昨天运动了一下，明天也要运动鸭。哎呀，多说了那么多废话，还是会想要好好的努力，有一个美好的未来hhh。看到有学长队伍状态真的十分不错呢，还是静下心来好好学习才是算法学习的正解呢！向他们学习！