【题目来源】
https://www.luogu.com.cn/problem/T145300
【题目描述】
DD 和 QQ 在玩游戏，DD 在地上画了一棵树（图论中的树），然后他告诉 QQ 这棵树的度数序列。QQ 马上说这不是一棵树。DD 认为自己被 QQ 鄙视了，他们吵了起来。
但 DD 随后发现自己算错了度数序列，QQ 说的是对的。DD 很奇怪为什么 QQ 反应得这么快。
现在给出一个图的度数序列，你需要做的就是像 QQ 一样：判断这是否可能是一棵树的度数序列。
【输入格式】
输入只有一行，首先给出一个整数 N，表示顶点个数。后面跟着 N 个整数，表示这个图的度数序列，每个数不超过 100。
【输出格式】
如果输入可能是一棵树的度数序列，则输出“Possible”，否则输出“Impossible”。
【输入样例一】
1 0
【输出样例一】
Possible
【输入样例二】
2 1 1
【输出样例二】
Possible
【输入样例三】
3 2 2 2
【输出样例三】
Impossible
【输入样例四】
3 1 2 1
【输出样例四】
Possible
【数据范围】
对于 100% 的数据，有1≤N≤100。
【算法分析】
● 依据图论握手定理，任意图中所有顶点的度数之和，等于图中边数的两倍。而树作为一种无环连通图，固定含有 n-1 条边。其中，n 是树中结点的个数。综上可知，若一个含 n 个结点的图，所有结点的度数之和等于 2*(n-1)，则该图满足树的度数必要条件。
● 两种情况需要特判
（1）结点数等于 1，但结点的度为 0。显然，这是树。
（2）结点数大于 1，但存在度为 0 的结点。显然，这不是树。
【算法代码】
#include <bits/stdc++.h> using namespace std; int main() { int flag=0,sum=0,n,x; cin>>n; for(int i=1; i<=n; i++) { cin>>x; sum+=x; if(x==0) flag=1; } if(n==1 && flag) cout<<"Possible"; if(sum==2*(n-1)) { if(n>1 && flag) cout<<"Impossible"; else cout<<"Possible"; } else cout<<"Impossible"; return 0; } /* in:1 0 out:Possible in:2 1 1 out:Possible in:3 2 2 2 out:Impossible in:3 1 2 1 out:Possible */
【参考文献】
https://blog.csdn.net/weixin_43346722/article/details/108209333
https://blog.csdn.net/m0_64281605/article/details/128194589
https://www.luogu.com.cn/problem/T230598
https://www.luogu.com.cn/problem/T145300
