[HDU5963]朋友

题目大意：

给定一棵\(n(n\le40000)\)个点的树，边权只能是\(0\)或\(1\)。一局游戏开始时，会确定一个结点作为根。AB轮流操作。当一方操作时，他们需要先选择一个不为根的点，满足该点到其父亲的边权为1; 然后找出这个点到根节点的简单路径，将路径上所有边的权值翻转。当一方无法操作时(即所有边的边权均为0)，另一方就获得了胜利。

共\(m(m\le40000)\)次操作，操作分为以下两种：

询问对于当前的树，如果以\(x\)为根节点开始游戏，哪方会获得胜利。
将\(x\)和\(y\)之间的边的边权修改为\(z\)。

思路：

找规律，答案仅与与根相连的\(1\)边个数的奇偶性有关。

源代码：

#include<set>

#include<cstdio>

#include<cctype>

#include<algorithm>

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

const int N=4e4+1;

bool b[N];

std::set<int> set[N];

int main() {

	for(register int T=getint();T;T--) {

		const int n=getint(),m=getint();

		for(register int i=1;i<n;i++) {

			const int u=getint(),v=getint();

			if(getint()) {

				set[u].insert(v);

				set[v].insert(u);

				b[u]^=1;

				b[v]^=1;

			}

		}

		for(register int i=0;i<m;i++) {

			if(getint()) {

				const int u=getint(),v=getint();

				const bool w=getint();

				if(!w&&set[u].count(v)) {

					set[u].erase(v);

					set[v].erase(u);

					b[u]^=1;

					b[v]^=1;

				}

				if(w&&!set[v].count(u)) {

					set[u].insert(v);

					set[v].insert(u);

					b[u]^=1;

					b[v]^=1;

				}

			} else {

				puts(b[getint()]?"Girls win!":"Boys win!");

			}

		}

		std::fill(&b[1],&b[n]+1,false);

		for(register int i=1;i<=n;i++) {

			set[i].clear();

		}

	}

	return 0;

}

巴特西

[HDU5963]朋友

[HDU5963]朋友

题目大意：

思路：

源代码：

最新文章

热门文章