设计的网站源代码怎么做,厦门seo关键词排名,昆明网站搜索引擎优化,自适应网站开发书籍Problem - G - Codeforces
题意#xff1a;
给定一棵n个节点的树#xff0c;请你减掉一些边#xff0c;使得剪掉后的每个树只有三个节点#xff0c; 如果可以#xff0c;第一行返回减掉边的数量#xff0c;第二行返回减掉边的编号#xff1b;如果无解#xff0c;输出…Problem - G - Codeforces
题意
给定一棵n个节点的树请你减掉一些边使得剪掉后的每个树只有三个节点 如果可以第一行返回减掉边的数量第二行返回减掉边的编号如果无解输出-1
思路
首先去观察样例 可以发现我们可以从叶子结点递归裁剪
Code
#include bits/stdc.h#define int long longusing namespace std;const int mxn2e510;
const int mxe2e510;struct ty{int to,next;
}edge[mxe2];vectorint ans;mappairint,int,int G; int N,u,v;
int tot0;
int head[mxn];void add(int u,int v){edge[tot].tov;edge[tot].nexthead[u];head[u]tot;
}
void G_init(){tot0;G.clear();ans.clear(); for(int i0;iN;i){head[i]-1;}
}
int dfs(int u,int fa){int cnt1;for(int ihead[u];~i;iedge[i].next){if(edge[i].tofa) continue;cntdfs(edge[i].to,u);}if(cnt3){ans.push_back(G[{u,fa}]);return 0;}return cnt;
}
void solve(){cinN;G_init();for(int i1;iN-1;i){cinuv;add(u,v);add(v,u);G[{u,v}]G[{v,u}]i;}if(N%3!0){cout-1\n;return;}int xdfs(1,0);if(ans.size()!N/3){cout-1\n;return;}coutN/3-1\n;for(int i0;ians.size()-1;i) coutans[i] \n[ians.size()-2];
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __1;cin__;while(__--)solve();return 0;
}
