yukicoder : No.2822 Lights Up! (Tree Edition)

解けたけどだいぶ手間取った。
https://yukicoder.me/problems/no/2822

問題

木を成す無向グラフが与えられる。
各辺には0/1の値が振られている。

ここで、K個の頂点対が与えられる。
頂点対を選択し、最短のパス上の辺に振られた値を0/1反転できる。
全辺の値を0にできるか判定せよ。

解法

各点をDFS post-order順で並べ替える。

また、頂点対のうち始点が一致する2つの対(A,B),(A,C)があったとする。
この場合、DFS post-order順でBがCの手前なら、(A,B)と(B,C)のように始点が異なる2つの対に分けることができる。
この手順を繰り返し、1つの始点に対し1つの頂点対のみ対応づくようにしよう。

点の並び順がDFS post-order順なので、(A,B)という頂点対があれば、Aから延びるパスはAの親方向になる。
そこで、DFSで点を訪問し、点Aの親方向の辺の値が1なら、頂点対(A,B)を1回選択しよう。

もし、親方向の辺の値が1なのに、その点始点とする頂点対がない場合、全辺の値を0にできない。

int N;
vector<int> E[202020];
string S;

int P[200005],D[202020];
int L[202020],re[202020];
int id;
int C[101010];
int dif[101010];

vector<int> tar[101010];
int K;

void dfs(int cur) {
	FORR(e,E[cur]) if(e!=P[cur]) D[e]=D[cur]+1, P[e]=cur, dfs(e);
	L[cur]=id++;
	re[L[cur]]=cur;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	for(i=1;i<N;i++) {
		cin>>x;
		E[x-1].push_back(i);
	}
	cin>>S;
	dfs(0);
	for(i=1;i<N;i++) C[i]=S[i-1]=='#';
	
	cin>>K;
	FOR(i,K) {
		cin>>x>>y;
		x--,y--;
		if(L[x]>L[y]) swap(x,y);
		tar[x].push_back(y);
	}
	FOR(i,N-1) {
		x=re[i];
		vector<pair<int,int>> T;
		FORR(e,tar[x]) T.push_back({L[e],e});
		sort(ALL(T));
		T.erase(unique(ALL(T)),T.end());
		
		if(T.size()>1) {
			FOR(j,T.size()-1) {
				tar[T[j].second].push_back(T[j+1].second);
			}
		}
		if(dif[x]!=C[x]) {
			if(T.empty()) {
				cout<<"No"<<endl;
				return;
			}
			y=T[0].second;
			dif[x]^=1;
			dif[y]^=1;
		}
		dif[P[x]]^=dif[x];
		
	}
	cout<<"Yes"<<endl;
	
	
}

まとめ

最初辺じゃなく点に0/1が振られてると勘違いし、悩んでしまった。