CodeTON Round 1 : E. Equal Tree Sums

とてもグダグダだった回。
https://codeforces.com/contest/1656/problem/E

問題

木を成す無向グラフが与えられる。
各点に、ゼロでない整数を割り当てることを考える。

各点に対し、その点が取り除かれたときに各連結成分において、頂点に割り当てられた整数の和が等しくなるようにせよ。

解法

SubTreeにおいて、頂点に割り当てられた整数の和が1または-1になるようにしていこう。
もし頂点vのSubTreeの総和が1なら、子頂点cのSubTreeの総和は-1と、符号を反転させるようにする。

そうすると各頂点は必ず(子頂点数+1)か-(子頂点数+1)の値を取ることになるので、0にはならない。

int T,N;
vector<int> E[101010];

int ret[101010];
int dfs(int cur,int pre,int d) {
	
	int sum=0;
	FORR(e,E[cur]) if(e!=pre) {
		sum+=dfs(e,cur,-d);
	}
	if(cur==pre) d=0;
	ret[cur]=d-sum;
	return d;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) E[i].clear();
		FOR(i,N-1) {
			cin>>x>>y;
			E[x-1].push_back(y-1);
			E[y-1].push_back(x-1);
		}
		
		FOR(i,N) if(E[i].size()>=2) {
			dfs(i,i,1);
			break;
		}
		FOR(i,N) cout<<ret[i]<<" ";
		cout<<endl;
	}
}

まとめ

DとE逆ならよかったのに…。