CF1141G

lijinmo · 2026-10-19 18:54:00 · 题解

解析

我们贪心地想，要使公司最少，那肯定要把 k 个不好城市的额度给度数最多的那 k 个。所以 r 就很简单了，把所有点的度从大到小排序，取第 k+1 个。若 k+1>n 则取 1。

那现在需要解决：要怎么分配？可以遍历树，每到一个点时保证它的父边已经完成分配。那么被我们钦定为不好城市的显然可以把全部子边赋成 1，正常情况下的可以枚举子边，每条子边赋的值为上次赋的值 +1（第一条子边赋 1），遇到父边的值就再 +1。这样确保了它用到的编号最多为它的度数。

于是就做完了，时间复杂度 \mathcal{O}(n \log n)。

AC 记录

:::success[参考代码]

#include<iostream>
#include<algorithm>
#include<vector>
#define int long long
using namespace std;
const int N=2e5+5;
int n,k;
struct node
{
    int z,id;
}d[N];
vector<pair<int,int>> v[N];
int ys[N];
bool flag[N];
inline bool cmp(node x,node y)
{
    return x.z>y.z;
}
inline int read(){int out=0,fh=1;char cc=getchar();while((cc>'9' || cc<'0') && cc!='-'){cc=getchar();}if(cc=='-'){fh=-1;}while(cc>'9' || cc<'0'){cc=getchar();}while(cc>='0' && cc<='9'){out=out*10+cc-'0';cc=getchar();}return out*fh;}
inline void write(int x){if(x<0){x=-x;putchar('-');}if(x==0){putchar('0');return ;}int num=0;char c[60];while(x){c[++num]=(x%10)+48;x/=10;}while(num){putchar(c[num--]);}}
inline string readstr(){string ans="";char cc=getchar();while(cc==' ' || cc=='\r' || cc=='\n'){cc=getchar();}while(cc!=' ' && cc!='\r' && cc!='\n' && cc!=EOF){ans+=cc;cc=getchar();}return ans;}
inline void writestr(string s){int sz=s.size();for(int i=0;i<sz;i++){putchar(s[i]);}}
inline char readchar(){char cc=getchar();while(cc==' ' || cc=='\r' || cc=='\n'){cc=getchar();}return cc;}
inline void dfs(int d,int fa,int fbs)
{
    if(flag[d])
    {
        for(auto t:v[d])
        {
            int v=t.first,h=t.second;
            if(v==fa) continue;
            ys[h]=1;
            dfs(v,d,1);
        }
        return ;
    }
    int tot=0;
    for(auto t:v[d])
    {
        int v=t.first,h=t.second;
        if(v==fa) continue;
        ++tot;
        if(tot==fbs) ++tot;
        ys[h]=tot;
        dfs(v,d,tot);
    }
}
signed main()
{
    n=read(),k=read();
    for(int i=1;i<n;i++)
    {
        d[i].id=i;
        int x=read(),y=read();
        ++d[x].z;
        ++d[y].z;
        v[x].push_back(make_pair(y,i));
        v[y].push_back(make_pair(x,i));
    }
    d[n].id=n;
    sort(d+1,d+1+n,cmp);
    for(int i=1;i<=k;i++)
    {
        flag[d[i].id]=true;
    }
    write(max(1LL,d[k+1].z));
    putchar('\n');
    dfs(1,0,0);
    for(int i=1;i<n;i++)
    {
        write(ys[i]);
        putchar(' ');
    }

    return 0;
}
/*
我是cjn,补肘啦,快速补充愤怒值
*/

:::