【树上操作】定长裁剪 CF1833 G

今天药忘吃喽~ 2024-03-18 00:38 73阅读 0赞

[Problem - G - Codeforces][]

题意：

给定一棵n个节点的树，请你减掉一些边，使得剪掉后的每个树只有三个节点，  
如果可以，第一行返回减掉边的数量，第二行返回减掉边的编号；如果无解，输出-1

思路：

首先去观察样例：

![b91522c171e043c798abcffaf577cd4c.png][]

可以发现我们可以从叶子结点递归裁剪

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=2e5+10;
    const int mxe=2e5+10;
    
    struct ty{
    	int to,next;
    }edge[mxe<<2];
    
    vector<int> ans;
    
    map<pair<int,int>,int> G; 
    
    int N,u,v;
    int tot=0;
    int head[mxn];
    
    void add(int u,int v){
    	edge[tot].to=v;
    	edge[tot].next=head[u];
    	head[u]=tot++;
    }
    void G_init(){
    	tot=0;
    	G.clear();
    	ans.clear(); 
    	for(int i=0;i<=N;i++){
    		head[i]=-1;
    	} 
    }
    int dfs(int u,int fa){
    	int cnt=1;
    	for(int i=head[u];~i;i=edge[i].next){
    		if(edge[i].to==fa) continue;
    		cnt+=dfs(edge[i].to,u);
    	}
    	if(cnt==3){
    		ans.push_back(G[{u,fa}]);
    		return 0;
    	}
    	return cnt;
    }
    void solve(){
    	cin>>N;
    	G_init();
    	for(int i=1;i<=N-1;i++){
    		cin>>u>>v;
    		add(u,v);
    		add(v,u);
    		G[{u,v}]=G[{v,u}]=i;
    	}
    	if(N%3!=0){
    		cout<<-1<<'\n';
    		return;
    	}
    	int x=dfs(1,0);
    	if(ans.size()!=N/3){
    		cout<<-1<<'\n';
    		return;
    	}
    	cout<<N/3-1<<'\n';
    	for(int i=0;i<ans.size()-1;i++) cout<<ans[i]<<" \n"[i==ans.size()-2];
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;cin>>__;
    	while(__--)solve();return 0; 
    }

[Problem - G - Codeforces]: https://codeforces.com/contest/1833/problem/G
[b91522c171e043c798abcffaf577cd4c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/eed87f582eb4408d83bf3010da4f5871.png