codeforce每日一题链接
题目链接
题目描述
给你一棵树,请你减掉一些边,使得剪掉后的每个树里只有三个节点,如果可以,第一行返回减掉边的数量,第二行返回减掉边的编号;如果不行输出-1。
样例
输入样例1
4
9
1 2
4 3
7 9
5 4
4 6
3 2
8 7
1 7
6
1 2
1 3
4 3
1 5
6 1
6
1 2
3 2
3 4
4 5
6 5
5
1 3
5 3
5 2
3 4
输出样例1
2
2 8
-1
1
3
-1
输入样例2
4
2
1 2
3
1 2
3 1
6
1 2
3 1
3 4
3 5
6 1
9
2 6
6 9
9 1
9 7
1 8
7 3
8 5
4 7
输出样例2
-1
0
1
2
2
4 3
算法
(树上dp) $O(n)$
我们只要dfs一下,dfs返回的是当前节点的子节点数量,如果当前节点和子节点的数量加起来等于3,就可以剪掉了,返回就是0。如果当前节点加上子节点的数量大于3,就一定无法减枝,无解,如果小于3,就直接返回就行了。
C++ 代码
// https://www.acwing.com/blog/content/34755/
#include<bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;
const int N = 2e5 + 10, M = N * 2, INF = 0x3f3f3f3f;
int n, m;
int e[M], ne[M], h[N], idx;
vector<int> res;
inline void add(int a, int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
inline int dfs(int u, int fa)
{
int t = 1;
for(int i=h[u];~i;i=ne[i])
{
int j = e[i];
if(j==fa) continue;
int d = dfs(j, u);
if(d==0) res.pd(i / 2);
t += d;
}
if(t==3) return 0;
else if(t<3) return t;
else return INF;
}
inline void solve()
{
memset(h, -1, sizeof h);
idx = 0;
res.clear();
cin>>n;
for(int i=1;i<n;i++){
int a, b;
cin>>a>>b;
add(a, b), add(b, a);
}
int d = dfs(1, -1);
if(d>=INF/2 || d) cout<<-1<<endl;
else{
cout<<res.size()<<endl;
for(auto u : res) cout<<u + 1<<" ";
cout<<endl;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin>>T;
while(T--)
{
solve();
}
return 0;
}