#C241123C. 旁观者

标签（Label）

• 博弈论

网址（Website）

题目详情 - 旁观者 - Super

题解 - 旁观者 - Super

题目（Problem）

输入数据 1

1 3
2
1
1 0
5
1 2 2 1
0 0 0 1 0
8
1 2 2 2 1 6 1
1 0 0 0 1 0 1 0

输出数据 1

yes
no
yes

【样例1解释】

在第一轮游戏中最后一个取得棋子一定是第 $2$ 个，所以小 $\text{C}$ 一定胜。

在第二轮游戏中小 $\text{C}$ 先取了 $1$ 号棋子，大 $\text{C}$ 如果取 $5$ 号棋子，那么小 $\text{C}$ 就只能取 $2$ 号棋子，大 $\text{C}$ 此时取 $3$ 号棋子，那么小 $\text{C}$ 就只能取 $4$ 号棋子，这样小 $\text{C}$ 就输了。

【样例2】

见选手目录下的 $bystander/bystander2.in$ 与 $bystander/bystander2.ans$。

该样例数据满足测试点 $5\sim7$ 的限制。

【样例3】

见选手目录下的 $bystander/bystander3.in$ 与 $bystander/bystander3.ans$。

该样例数据满足测试点 $8\sim10$ 的限制。

【样例4】

见选手目录下的 $bystander/bystander4.in$ 与 $bystander/bystander4.ans$。

该样例数据满足测试点 $11\sim14$ 的限制。

【样例5】

见选手目录下的 $bystander/bystander5.in$ 与 $bystander/bystander5.ans$。

该样例数据满足测试点 $15\sim18$ 的限制。

【样例6】

见选手目录下的 $bystander/bystander6.in$ 与 $bystander/bystander6.ans$。

该样例数据满足测试点 $19\sim20$ 的限制。

题解（Solution）

容易发现依赖关系构成了一棵树。

考虑最优操作时小 $\text{C}$ 和大 $\text{C}$ 会怎么取棋子，很明显，二人一定会贪心去取棋子，而且肯定是想尽量把对方的颜色的棋子取完，这样最后剩下的就是自己胜利的颜色。

那么对于 $p_i=1$ 的点，我们就想到了答案。接下来考虑将这个思想拓展成一棵正常的树的形式。容易发现父亲的颜色一定不影响最后的答案。考虑如果一些点有一个父亲，谁会更希望去多花一步取掉这个父亲呢？如果这些点白子和黑子数量不同，那么黑的多小 $\text{C}$ 肯定更希望删掉这个点，白的多大 $\text{C}$ 肯定更希望删掉这个点，一样多的时候两个人只能轮流删，那么删到最后的人就输了，具体来讲，如果 $n$ 为奇数，小 $\text{C}$ 最后删完的一定是黑子，那么小 $\text{C}$ 输，否则大 $\text{C}$ 就输了。

考虑使用 $f_i$ 表示以 $i$ 为子树时白子和黑子数量之差（白子为正），那么当 $f_i>0$ 的时候，大 $\text{C}$ 更希望删掉这个节点来解锁后面的节点，因此他会多花一步，那么相当于多了一个白子，则 $f_i\leftarrow f_i+1$ ；如果 $f_i<0$ ，同样的道理，有 $f_i\leftarrow f_i-1$ ，否则，根据 $n$ 的奇偶性判断，因为白色的和黑色的相等，如果 $n$ 为奇数，那么最后拿走父节点的一定是在奇数次行动的小 $\text{C}$ ，因此 $f_i\leftarrow f_i-1$ ，否则就是在偶数次行动的大 $\text{C}$ ，有 $f_i\leftarrow f_i+1$ 。

最后只需要判断 $f_i$ 大于 $0$ 还是小于 $0$ 就好了，特别的，容易发现如果 $f_i=0$ ，由于是小 $\text{C}$ 先走，所以最后一定是大 $\text{C}$ 取走黑色棋子，还是小 $\text{C}$ 输。

时间复杂度：$O(\sum n)$ 。

出题者题解

代码（Code）

15分

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
#define show(a) For(i,1,n) cerr<<a[i]<<' ';cerr<<'\n'
using namespace std;
#define P pair<int,int> 
#define int long long
#define x first
#define y second
#define in(x,l,r) (l<=x && x<=r)
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}template<typename G>
void write(G x){
	if(x<0) putchar('-'),write(-x);
	else if(x<=9) putchar('0'+x);
	else write(x/10),putchar('0'+x%10);
}constexpr int inf = 0x3f3f3f3f3f3f3f3f;
constexpr int N = 1012345;
bool ST;int tid,Tt;

vector<int> ft[N];
int n,c[N];

namespace Q{
	void Solve1(){
		int s1=0, s2=0;
		For(i,2,n){
			s1 += c[i]==0;
			s2 += c[i]==1; 
		}printf("%s\n", (s1>s2) ? "yes" : "no");
	}
}

void Solve(){
	For(i,1,n) ft[i].clear();
	
	n=rd();For(x,2,n){
		int y=rd();
		ft[x].emplace_back(y);
		ft[y].emplace_back(x);
	}For(i,1,n) c[i]=rd();
	
	if(in(tid,5,7)) return Q::Solve1();
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("bystander.in","r",stdin);
	freopen("bystander.out","w",stdout);
	tid=rd();Tt=rd();double Tim=clock();
	while(Tt--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}

100分

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
#define show(a) For(i,1,n) cerr<<a[i]<<' ';cerr<<'\n'
using namespace std;
#define P pair<int,int> 
#define int long long
#define x first
#define y second
#define in(x,l,r) (l<=x && x<=r)
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}template<typename G>
void write(G x){
	if(x<0) putchar('-'),write(-x);
	else if(x<=9) putchar('0'+x);
	else write(x/10),putchar('0'+x%10);
}constexpr int inf = 0x3f3f3f3f3f3f3f3f;
constexpr int N = 1012345;
bool ST;int tid,Tt;

vector<int> ft[N];
int n,c[N],f[N];

void dfs(int x){
	if(ft[x].empty()) return f[x]=c[x]?-1:1, void();
	f[x] = 0;
	for(auto y:ft[x]) dfs(y), f[x] += f[y];
	if(f[x] > 0) f[x]++;
	else if(f[x] < 0) f[x]--;
	else f[x] += n&1?-1:1;
}

void Solve(){
	n=rd();For(i,1,n) ft[i].clear();
	For(x,2,n) ft[rd()].emplace_back(x);
	For(i,1,n) c[i]=rd();
    dfs(1);
	if(f[1]>0) puts("yes");
	else puts("no");
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("bystander.in","r",stdin);
	freopen("bystander.out","w",stdout);
	tid=rd();Tt=rd();double Tim=clock();
	while(Tt--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}