【2020.8.24NOIP模拟赛】这是一棵树吗?

题目描述
DD和QQ在玩游戏，DD在地上画了一棵树（图论中的树），然后他告诉QQ这棵树的度数序列。QQ马上说这不是一棵树。DD认为自己被QQ鄙视了，他们吵了起来。
但DD随后发现自己算错了度数序列，QQ说的是对的。DD很奇怪为什么QQ反应得这么快。
现在给出一个图的度数序列，你需要做的就是像QQ一样：判断这是否可能是一棵树的度数序列。
输入格式
输入只有一行，首先给出一个整数 N，表示顶点个数,后面跟着 N 个整数，表示这个图的度数序列，每个数不超过 100。
输出格式
如果输入可能是一棵树的度数序列，则输出“Possible”，否则输出“Impossible”。
输入输出样例
输入 #1
1 0

输出 #1
Possible

输入 #2
2 1 1

输出 #2
Possible

输入 #3
3 2 2 2

输出 #3
Impossible

输入 #4
3 1 2 1

输出 #4
Possible

说明/提示

对于 100% 的数据，有 1≤N≤100。
解题思路
这道题虽然看起来数据不大，只有 1≤N≤100 的数据，基本上可以用O(n2)乃至O(n3)的算法，然而这道题的正解是O(n)的数学方法，我的O(n2)暴力也才70，WA了3个点 （虽然有可能是我本身的问题） …
毒瘤出题人YMW！
那么这道题应该怎么做呢？我们先分析题目，题目中所谓的 “度” 很明显是入度+出度。我们想一想如何用度表示点的数量：对于每个点来说，入度只有可能是1，也就是它的父亲（这是一棵树）。那么我们对于每个点的度 -1，累加后 +2 即可。为什么要 +2 呢？一个是根节点没有父亲，另一个是根节点本身也是一个点（PS：为什么要单独说根节点呢？我们这里的度除去入度后剩下的是它的出度，也就是儿子，是不包括它本身的，除了根节点以外的点的值都在计算它的父亲是计算过了）
如果累计后的值正好等于节点数，那么它就有可能。
实际上还有个特判：当n==1时，唯一的度只能为0
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int n,a,ans;

int main()
{
	cin>>n;
	if(n==1)
	{
		scanf("%d",&a);
		if(a==0)
			printf("Possible");
		else
			printf("Impossible");
		return 0;
	}	
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a);
		if(a==0)
		{
			printf("Impossible");
			return 0;
		}
		a--;
		ans+=a;
	}
	if(ans+2==n)
		printf("Possible");
	else
		printf("Impossible");
}