蒟蒻求助,Subtask#1 hack没过,100pts求调
  • 板块P3942 将军令
  • 楼主FriedrichC
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/11/13 17:05
  • 上次更新2023/10/27 03:05:22
查看原帖
蒟蒻求助,Subtask#1 hack没过,100pts求调
625380
FriedrichC楼主2022/11/13 17:05

rt

#include<bits/stdc++.h>
#define int long long
#define maxn 100010
using namespace std;
int n,k,lab;
struct node{
    int id,d;
    bool operator<(const node &rhs)const{
        return d<rhs.d;
    }
};
priority_queue<node>q;
struct line{int to,pre;}b[maxn<<1];
int head[maxn<<1],t;
inline void ad(int x,int y)
{
    t++;
    b[t].to=y;
    b[t].pre=head[x];
    head[x]=t;
}
int dep[maxn],f[maxn];
void dfs1(int x,int fa)
{
    dep[x]=dep[fa]+1;
    f[x]=fa;
    for(int i=head[x];i;i=b[i].pre)
    {
        int y=b[i].to;
        if(y==fa)continue;
        dfs1(y,x);
    }
}
bool vis[maxn];
void dfs2(int x,int fa,int len)
{
    vis[x]=1;
    if(len==k)return;
    for(int i=head[x];i;i=b[i].pre)
    {
        int y=b[i].to;
        if(y==fa)continue;
        dfs2(y,x,len+1);
    }
}
int get_kth_fa(int x)
{
    int cnt=0;
    while(cnt<k)
    {
        x=f[x];
        cnt++;
    }
    return x;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k>>lab;
    for(int i=1;i<=n-1;++i)
    {
        int x,y;
        cin>>x>>y;
        ad(x,y); ad(y,x);
    }
    dfs1(1,0);
    for(int i=1;i<=n;++i)q.push({i,dep[i]});
    int ans=0;
    while(!q.empty())
    {
        int x=q.top().id; q.pop();
        if(vis[x])continue;
        ans++;
        int fa=get_kth_fa(x);
        dfs2(fa,-1,0);
    }
    cout<<ans<<endl;
	return 0;
}

2022/11/13 17:05
加载中...