TopCoderOpen 2017 Round1B Hard SubtreeSumHash

Mediumの方が難しくない…？
https://community.topcoder.com/stat?c=problem_statement&pm=14562

問題

木を成すグラフが与えられる。
各頂点vには重さW[v]が設定されている。

この木の部分木の重さの合計をAとしたとき、部分木のスコアは整数xに対しx^Aとする。
全部分木に対するスコアの合計を求めよ。

解法

各頂点vに対し、そのvを根とし、v以降の番号の頂点だけで構成される部分木のスコアを求めていこう。

ある木Tのスコアをx^Aとする。
ここに頂点v'を1つ足すと、その木のスコアはx^(A+W[v'])となる。
よって部分木としてv'を含まないものと含むものの和はx^A*(1+x^W[v'])となる。

頂点vを根とし、vを含むSubTreeのスコアの総和をS(v)とする。
木DPの要領でS(v)を更新して以降。
vの子頂点cに対しS(c)を求めると、cを含む場合と含まない場合を考慮してS(v) *= (1+S(c))の要領でS(v)を更新していける。

ll mo=1000000007;
ll modpow(ll a, ll n = mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

class SubtreeSumHash {
	public:
	
	int N;
	int W[51];
	vector<int> E[51];
	
	ll hoge(int cur,int pre,int more) {
		ll ret=W[cur];
		FORR(r,E[cur]) if(r!=pre && r>=more) (ret *= 1+hoge(r,cur,more))%=mo;
		return ret;
	}
	
	int count(vector <int> weight, vector <int> p, int x) {
		N=weight.size();
		int i;
		FOR(i,N) {
			E[i].clear();
			W[i]=modpow(x,weight[i]);
		}
		FOR(i,N-1) {
			E[i+1].push_back(p[i]);
			E[p[i]].push_back(i+1);
		}
		ll ret=0;
		FOR(i,N) ret += hoge(i,-1,i);
		return ret % mo;
		
	}
}

まとめ

1Bはだいぶ参加者少ないけど、1Cはどれだけ残るんだろう。