codeforces 963B Destruction of a Tree

codeforces 963B Destruction of a Tree

​​ 题目描述 You are given a tree (a graph with n vertices and n−1 edges in which it’s possible to reach any vertex from any other vertex using only its edges). A vertex can be destroyed if this vertex has even degree. If you destroy a vertex, all edges connected to it are also deleted. Destroy all vertices in the given tree or determine that it is impossible. 输入输出格式 输入格式： The first line contains integer n ( 1<=n<=2⋅105 ) — number of vertices in a tree. The second line contains n integers p1​,p2​,…,pn​ ( 0<=pi​<=n ). If pi​≠0 there is an edge between vertices i and pi​ . It is guaranteed that the given graph is a tree. 输出格式： If it’s possible to destroy all vertices, print “YES” (without quotes), otherwise print “NO” (without quotes). If it’s possible to destroy all vertices, in the next n lines print the indices of the vertices in order you destroy them. If there are multiple correct answers, print any. 输入输出样例 输入样例#1： 复制 5 0 1 2 1 2 输出样例#1： 复制 YES 1 2 3 5 4 输入样例#2： 复制 4 0 1 2 3 输出样例#2： 复制 NO 说明 In the first example at first you have to remove the vertex with index 1 (after that, the edges (1, 2) and (1, 4) are removed), then the vertex with index 2 (and edges (2, 3) and (2, 5) are removed). After that there are no edges in the tree, so you can remove remaining vertices in any order. 题解：jpy大爷的题解​ 考虑偶数个点的话一定是不可删的 为什么因为偶数个点即有奇数条边 每次删除减少至少是偶数条边 那么最后怎么也无法减少到0 如果是奇数个点的话我们考虑如何构造可行解 一组可行解我们考虑将树分成偶子树&奇子树来看考虑我把当前节点当根 如果我是偶子树的根的话我一定有奇数个奇子树&奇数个偶子树 那么先把偶子树搞定再做根再做奇子树即可

#include#include#includeusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if(ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=2e5+10;struct node{ int y,next;}data[N<<1];int h[N],size[N],num,n;inline void get_size(int x,int fa){ size[x]=1; for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if (y==fa) continue; get_size(y,x);size[x]+=size[y]; }}inline void dfs(int x,int fa){ for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if (y==fa) continue; if (size[y]&1) continue;dfs(y,x); }printf("%d\n",x); for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if(y==fa) continue; if(size[y]&1) dfs(y,x); }}int main(){// freopen("cf963b.in","r",stdin); n=read();if(n%2==0) {puts("NO");return 0;} puts("YES"); for (int i=1;i<=n;++i){ int x=read(),y=i;if (!x) continue; data[++num].y=y;data[num].next=h[x];h[x]=num; data[++num].y=x;data[num].next=h[y];h[y]=num; }get_size(1,1);dfs(1,1); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。