TopCoder SRM 799 : Div2 Hard MapleTreeEasy

Div1Mediumよりだいぶ簡単。
https://community.topcoder.com/stat?c=problem_statement&pm=15470&rd=18494

問題

木を成すN頂点の無向グラフが与えられる。
このうち、頂点をいくつか選んだとする。

選んだ頂点群を連結に保つ辺と頂点だけ残したグラフがCoolであるとは、次数が3以上の点を含まないものとする。
頂点の選びかた2^N-1通りのうち、Coolなものは何通りか。

解法

残したグラフが長さLのパスであるとき、間の(L-1)頂点は選んでも選ばなくてもよいので、両端の頂点を定めるとそのような頂点の選び方は2^(L-1)通りとなる。
あとは、O(N^2)かけてパスの両端を総当たりしていこう。

ll ret;
vector<int> E[55];

class MapleTreeEasy {
	public:
	void dfs(int cur,int pre,int start,int d) {
		if(start<cur) ret+=1LL<<(d-1);
		FORR(e,E[cur]) if(e!=pre) dfs(e,cur,start,d+1);
		
	}
	long long count(vector <int> p) {
		int N=p.size()+1;
		
		int i,j;
		FOR(i,N) E[i].clear();
		FOR(i,p.size()) {
			E[p[i]].push_back(i+1);
			E[i+1].push_back(p[i]);
		}
		ret=N;
		FOR(i,N) dfs(i,i,i,0);
		return ret;
	}
}

まとめ

累積和とか使うとO(N)でも解けるかな？