建设银行网站上不去,python编程100例,下载图片的网站建设,wordpress 访客ipProblem - 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;
}
