TopCoderOpen 2021 Regional Qualification Round1 : Div1 Medium TreeTokens

なんか拘束時間長そうなので、イベントは不参加。コンテストもリアルタイム参加はしてないです。
https://community.topcoder.com/stat?c=problem_statement&pm=17112&rd=18769

問題

N頂点の木を成すグラフが与えられる。
先手が、各頂点にいくつかトークンを配置したとする。
後手は以下の処理を任意回数行い、トークンを動かせる。

• トークンが2個以上ある頂点を選択し、1つトークンを取り除くのと引き換えに1つトークンを隣接頂点に動かす。

木の根が与えられる。
先手は、後手がどうやっても根にトークンを持ってこれないような、トークンの初期配置を考えたい。
そのうち、総トークン数が最大のものはいくつになるか。

解法

根頂点からの距離がDの頂点には、(2^D)-1個までトークンを置くことができる。
ただし、その根頂点に子頂点がある場合、代わりに子頂点に(2^(D+1))-1個トークンを置いた方が良い。

この考察を踏まえると、最適な置き方は、

• 最も深い葉頂点に、(2^D)-1個トークンを置く。
• その葉頂点から根頂点までのパス上の頂点は、トークンを置いてはならない。
• 以後、残された最も深い葉頂点にトークンを置くのだが、その際は祖先の最寄りのトークンを置いてはならない頂点からの距離がD'の場合、(2^D')-1個トークンを置くようにする。

上記処理をそのまま書くと何度もDFSを繰り返す羽目になりそうだが、ちょっと書き換えるとO(N)で書ける。

vector<int> E[101010];
ll p2[101010];
const ll mo=1000000007;
class TreeTokens {
	public:
	
	pair<ll,ll> dfs(int cur,int pre,int d) {
		if(E[cur].size()==1) {
			return {0,d};
		}
		else {
			pair<int,int> p={0,0};
			FORR(e,E[cur]) if(e!=pre) {
				auto q=dfs(e,cur,d+1);
				(p.first+=q.first)%=mo;
				if(p.second<=q.second) {
					if(p.second) p.first+=p2[p.second-d]-1;
					p.second=q.second;
				}
				else {
					p.first+=p2[q.second-d]-1;
				}
			}
			p.first%=mo;
			return p;
		}
	}
	
	int placeMax(int N, int G, int L, int seed) {
		ll state = seed;
		int i;
		p2[0]=1;
		FOR(i,N) {
			E[i].clear();
			p2[i+1]=p2[i]*2%mo;
		}
		for(i=1;i<N;i++) {
			state = (state * 1103515245 + 12345)%(1LL<<31);
			int tmp = (state / 1000)%L;
			int p = max(0, i-1-tmp);
			E[i].push_back(p);
			E[p].push_back(i);
		}
		ll ret=0;
		FORR(e,E[G]) {
			auto p=dfs(e,G,1);
			ret+=p.first;
			ret+=p2[p.second]-1;
		}
		return (ret%mo+mo)%mo;
	}
}

まとめ

出てたらレートどうなってたかな…。