G.Guide(20202021ICPC,NERC,NorthernEurasiaOnsite题解)xiaodangao

题目链接：G.Guide
思路：想了好久。。贪心的想法是在一颗最长链上进行不回溯操作，我们需要一遍dfs标记出最长链，然后进行第二次dfs寻找答案，我们必须让dfs“死”在最长链上，方法是如果一个节点的子节点在最长链上，那么最后再进行dfs操作。然后在dfs中记录当前标记的非最长链上的点的数量，如果达到了$k-最长链上点的数量$那么需要立即进行回溯到最近的最长链上的点，然后结束操作。最后再加上最长链上的某些点就可以了。PS:代码写的很麻烦
$Code:$

#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) (x&(-x))
#define ch() getchar()
#define pc(x) putchar(x)
using namespace std;

template<typename T>void read(T&x){
static char c;static int f;
for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
static char q[65];int cnt=0;
if(x<0)pc('-'),x=-x;
q[++cnt]=x%10,x/=10;
while(x)
    q[++cnt]=x%10,x/=10;
while(cnt)pc(q[cnt--]+'0');
}

const int N = 1e2+10;
int _,k,n,cnt;
vector<int>G[N],now,ans,ans1;
int mx = -1,ret = 1;
bool st[N];
void dfs(int id,int high){//记录
    now.pb(id);
    for(auto p:G[id])dfs(p,high+1);
    if(mx < high){mx = high;ans = now; }
    now.pop_back();
}

bool flag = false,judge = true;
void dfs2(int id){
    int c = -1;
    if(flag == true)return ;
    cnt++;ans1.pb(id);
    if(st[id])ret++;
    int fr = cnt - ret;
    if(fr + (int)ans.size() >= k){
        flag = true;
        return ;
    }
    int h = cnt;
    for(auto p:G[id]){
        if(st[p] == true){c = p;continue; }
        dfs2(p);
        if(judge == true)return ;
        if(flag == true and st[id] == true){
            if(ans1[(int)ans1.size()-1]!=id)
            ans1.pb(id);
            judge = true;
            return ;
        }
        if(ans1[(int)ans1.size()-1]!=id)
        ans1.pb(id);
    }
    if(c != -1){
        dfs2(c);
        if(judge == true)return ;
        if(flag == true and st[id] == true){
        if(ans1[(int)ans1.size()-1]!=id)
        ans1.pb(id);
        judge = true;
        return ;
    }
    if(ans1[(int)ans1.size()-1]!=id)
        ans1.pb(id);
        return ;
    }
    return ;
}
void solve(){
    read(_);
    while(_--){
        mx = -1;
        flag = false;judge = false;
        ans1.clear();
        ret = 0;
        now.clear();
        memset(st,0,sizeof st);
        read(n);read(k);
        rep(i,1,n)G[i].clear();
        int t;
        cnt = 0;
        rep(i,2,n)read(t),G[t].pb(i);
        dfs(1,0);
        for(auto p:ans)st[p] = true;
        dfs2(1);
        int s = ans1[(int)ans1.size()-1];
        flag = false;
        for(auto p:ans){
            if(p == s){flag = true;continue;}
            if(flag == true and cnt < k)cnt++,ans1.pb(p);//,printf("%d ",p);
        }
        printf("%d\n",(int)ans1.size()-1);
        for(auto p:ans1)printf("%d ",p);pc('\n');
    }
}
signed main(){solve();return 0; }

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章