【SRM635】Div2 900 TreeAndPathLength2

    题目大意：求是否存在这样的一棵树，有n个节点和s条长度为2的简单路径，其中A->B->C和C->B->A算同一种。

    分析：随便找一个点为根root，那么路径有两种，一种是一个点到其父亲再到其父亲的父亲，第二种是一点到其父亲再到其兄弟节点。

    设节点x的儿子节点数为sons[x]，则第一种路径的条数为n-1-sons[root]，第二种路径的条数为所有sons[x]*(sons[x]-1)/2之和。

    设f[i][j]，i表示除root外所有节点的sons之和为i，j表示这些节点有j条长度为2的路径，f[i][j]=1表示这样的图存在。

    最后枚举sons[root]，判断是否存在这样的图即可。

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>

using namespace std;


class TreeAndPathLength2 {
public:
	string possible(int n, int s) {
		int arr[55][1010];
		memset(arr,0,sizeof(arr));
		arr[0][0]=1;
		for (int i=1;i<=n;i++)
		for (int j=0;j<i;j++)
		for (int k=0;k<=s && k+(i-j)*(i-j-1)/2<=s;k++) if (arr[j][k])
			arr[i][k+(i-j)*(i-j-1)/2]=1;
		int flag=0;
		for (int i=1;i<n;i++) if (i*(i-1)/2+n-i-1<=s) if (arr[n-1-i][s-(i*(i-1)/2+n-i-1)]) flag=1;
		if (flag) return "Possible";else return "Impossible";
	}
};