TopCoder SRM 698 Div2 Hard SubtreeSum

典型寄りな問題だと思うけど、Div2とはいえ正答者少なめ。
https://community.topcoder.com/stat?c=problem_statement&pm=14392

問題

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

この木におけるすべての部分木に対し、含まれる頂点のX[i]のbitwise-orを取った値の総和を求めよ。

解法

bitwise-orを逐一考慮するのは面倒なので、各bitに対してそれぞれ考えよう。
Y(i,d) := X[i]の下からd bit目の値 (dは0-index)
とする。
各dを総当たりし、部分木中にY(i,d)が1個でも1となる頂点があるケースの総和S(d)を求めて、S(d)*2^dを答えに計上すればよい。

S(d)を求めるパートは典型的な木DPかな。
SubTree中にある、1を1個も含まない部分木の数と、1を1個以上も含む部分木の数を葉から順に求めていく。

class SubtreeSum {
	public:
	
	int getSum(vector <int> p, vector <int> x) {
		ll mo=1000000007;
		int i,j;
		int N=x.size();
		vector<int> E[51];
		FOR(i,N-1) E[p[i]].push_back(i+1);
		
		ll tot=0;
		FOR(i,30) {
			ll ret=0;
			ll num[2][50]={};
			
			for(j=N-1;j>=0;j--) {
				num[(x[j]>>i)&1][j]=1;
				FORR(r,E[j]) {
					ll a0=num[0][j],a1=num[1][j];
					num[0][j] = a0 * (1+num[0][r]);
					num[1][j] = a1 * (1+num[0][r] + num[1][r]) + a0 * num[1][r];
				}
				ret += num[1][j];
			}
			
			tot += ((ret%mo)<<i)%mo;
		}
		return tot % mo;
		
	}
}

まとめ

bitwise-orの処理が面倒→最初から各bitだけ注目すればよい、と気づけば簡単。