CF1833G Ksyusha and Chinchilla 题解

Iniaugoty · 2023-06-18 13:37:57 · 题解

problem

在一棵树上删去一些边，使得形成的几个连通块，都有且仅有 3 个结点。输出：删边后连通块的数量和删去的边的编号。

solution

• - 若 $size_i=3$，把 $i$ 与其父结点的连边删掉。因为已经不在原图上了，为了不影响其他点的计算，令 $size_i\gets0$。 - 若 $size_i<3$，啥也不用干。 - 若 $size_i>3$，想一下可以发现，这样就无法形成大小 $3$ 的连通块了，故标记一下没有答案。

为了方便处理，设结节点为 1，其父节结为 0。

code

#include<bits/stdc++.h>
#define N 200005
using namespace std;
int head[N],cnt;//head[i] 表示起点为 i 的第一条边
struct star{//链式前向星存边
    int next,to,id;//next 是下一条边，to 是边的终点，id 是边的编号
}e[N<<1];//无向边二倍空间！
void add(int u,int v,int w){//加边函数
    e[++cnt].next=head[u];
    e[cnt].to=v;
    e[cnt].id=w;
    head[u]=cnt;
}
int T,n,size[N];//T 是数据组数，n 是点数
bool ans,cut[N];//ans 表示是否有答案，cut[i] 表示是否要删去编号 i 的边
void dfs(int step,int father){//step 是当前结点，father 是其父结点
    if(!ans) return;//如果已经确定没有答案，就返回
    int f=0;//如果要删边，要删的边的编号
    for(int i=head[step];i;i=e[i].next)
        if(e[i].to==father) f=e[i].id;//记录编号
        else dfs(e[i].to,step),size[step]+=size[e[i].to];//递归子节点，并计算 size
    size[step]++;//算上自己
    if(size[step]==3) size[step]=0,cut[f]=1;//删边
    //如果 step 是根结点，此时 f 就是 0，不影响 cut 数组，所以不用特判
    else if(size[step]>3) ans=0;//可以确定没有答案
}
signed main(){
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>T;
    while(T--){
        for(int i=1;i<=n;i++){//不要 memset！
            head[i]=size[i]=cut[i]=0;//不要 memset！！
            e[(i<<1)-1]=e[i<<1]={0,0,0};//不要 memset！！！
        }//除非是 bool 型，否则多测清空不要用 memset，容易超时
        cin>>n,cnt=0;
        for(int i=1,u,v;i<n;i++)
            cin>>u>>v,add(u,v,i),add(v,u,i);//无向图建双向边
        ans=!(n%3);//若 n 不是 3 的倍数，直接标记没有答案
        dfs(1,0);//求答案
        if(!ans) cout<<"-1\n";//没有答案直接输出 -1
        else{
            cout<<n/3-1<<"\n";//删掉的边数
            for(int i=1;i<n;i++)//遍历每条边
                if(cut[i]) cout<<i<<" ";//输出要删的
            cout<<"\n";
        }
    }
    return 0;
}