CF638C题解

我们可以针对一个顶点只能同时修一条边这个条件设计方案。

由于每条边都要修一遍，同样某天修理的方案放在哪一天修都无所谓，我们采用贪心的策略，在原有的方案上尽可能多地修边。

根据上面的性质，我们只需要将同一顶点的边放在不同的某天修理的方案中，使方案尽可能的少即可。
跑一遍 dfs，用 std::vector<int> 记录修理的方案就行了。

上述记录方案的过程中对于一个假定的根节点（根节点为 \(1\) 会比较好处理）会将边分别放入一个方案中，在向下遍历的过程中的节点都会有连接父节点的边被放入已有的一个方案中，所以会出现节点最大度数个方案，即最短时间为节点的最大度数。

代码如下。

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
typedef pair<int,int> pii;
constexpr int MAXN=2e5+10;
int n,deg[MAXN],maxdeg,cnt;
vector<pii> e[MAXN];
vector<int> g[MAXN];
void add(int u,int v,int id){
    e[u].pb({v,id});
}
void dfs(int u,int fa,int gr){
    int p=1;
    for(int i=0;i<e[u].size();++i){
        if(e[u][i].first!=fa){
            if(p==gr)++p;
            g[p].pb(e[u][i].second);
            cnt=max(p,cnt);
            ++p;
            dfs(e[u][i].first,u,p-1);
        }
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1,u,v;i<n;++i){
        scanf("%d%d",&u,&v);
        add(u,v,i);add(v,u,i);++deg[u];++deg[v];
    }
    for(int i=1;i<=n;++i)maxdeg=max(deg[i],maxdeg);
    printf("%d\n",maxdeg);
    dfs(1,0,0);
    for(int i=1;i<=cnt;++i){
        printf("%d ",g[i].size());
        for(int j:g[i]){
            printf("%d ",j);
        }
        puts("");
    }
    return 0;
}