洛谷P16411 [Algo Beat Contest 004 G] Go Playing with Reimu题解

Go Playing with Reimu

思路

话说这题为啥是青来着？

考虑如果没有修改怎么做。设 $d{p}_i$ 为当前棋子在 $i$ 点，$d{p}_i=1$ 表示先手必胜，$d{p}_i=0$ 表示后手必胜。转移很简单，如果 $i$ 的儿子中有任意一个点的 $dp$ 值为 $0$，则 $d{p}_i=1$（先手必胜），因为先手可以将棋子移动到那个点。否则，如果 $i$ 的所有儿子的 $dp$ 值都为 $1$，则 $d{p}_i=0$（后手必胜）。这里的先后手指的是当前状态下的先后手，不是初始状态下的先后手。

考虑带删除怎么做。运用树链剖分的思想，设 $g_i$ 表示 $i$ 的所有轻儿子中有多少 $dp$ 值为 $0$。考虑如何求 $d{p}_i$，如果 $g_i>0$，则 $d{p}_i=1$。否则如果 $g_i=0$，则 $d{p}_i$ 的值只与 $i$ 所在的重链上，在 $i$ 的子树中且离 $i$ 最近的满足 $g>0$ 的点的深度有关。

于是考虑对于每条重链开一个 set 维护重链上所有 $g>0$ 的点的深度，每次删除叶子节点就暴力跳父亲，如果当前点连向父亲的点是轻边就暴力改父亲的 $g$ 和 $dp$ 的值。否则直接修改所在重链的 set 然后跳到重链的顶端。

代码

根据重链剖分理论，暴力跳的复杂度是 $O(\log N)$。加上 set 总复杂度为 $O(N{\log }^{2}N)$，常数非常小。虽然在删除节点之后重链可能已经不再是重链，但是这并不影响复杂度。

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n,q,fa[N],g[N],si[N],tp[N],h[N],dep[N];
vector<int> a[N]; 
bool dp[N];//1 先手赢 0 后手赢 
set<int> s[N];
void solve(int x)
{
	if(!dp[x]&&tp[x]==x) g[fa[x]]--;
	auto it=s[tp[x]].find(dep[x]);
	if(it!=s[tp[x]].end()) s[tp[x]].erase(it);
	if(g[x]) dp[x]=1,s[tp[x]].insert(dep[x]);
	else
	{
		auto it=s[tp[x]].lower_bound(dep[x]);
		if(it==s[tp[x]].end()) dp[x]=0;
		else dp[x]=(*it-dep[x]+1)%2;
	}
	if(!dp[x]&&tp[x]==x) g[fa[x]]++;
}
void dfs(int x)
{
	si[x]=1,dep[x]=dep[fa[x]]+1;
	for(int i=0;i<a[x].size();i++)
		if(a[x][i]!=fa[x])
		{
			fa[a[x][i]]=x;
			dfs(a[x][i]);
			if(si[h[x]]<si[a[x][i]]) h[x]=a[x][i];
			si[x]+=si[a[x][i]];
			if(!dp[a[x][i]]) dp[x]=1;
		}
}
void dfss(int x)
{
	if(h[x]) tp[h[x]]=tp[x],dfss(h[x]);
	for(int i=0;i<a[x].size();i++)
		if(a[x][i]!=fa[x]&&a[x][i]!=h[x]) 
		{
			tp[a[x][i]]=a[x][i],dfss(a[x][i]);
			if(!dp[a[x][i]]) g[x]++;
		}
	if(g[x]) s[tp[x]].insert(dep[x]);
	else if(!h[x]) s[tp[x]].insert(dep[x]+1);//重链底端的点可能要特判一下 
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		a[u].push_back(v),a[v].push_back(u);
	}
	dfs(1);
	tp[1]=1;
	dfss(1);
	cin>>q;
	if(dp[1]==1) cout<<"Marisa\n";
	else cout<<"Reimu\n";
	while(q--)
	{
		int x;
		cin>>x;
		s[tp[x]].erase(dep[x]+1);	
		if(tp[x]!=x) s[tp[fa[x]]].insert(dep[x]);
		else g[fa[x]]--;
		while(x!=1)
			if(tp[x]==x) solve(fa[x]),x=fa[x];
			else solve(tp[x]),x=tp[x];
		solve(1);
		if(dp[1]==1) cout<<"Marisa\n";
		else cout<<"Reimu\n";
	}
	return 0;
}

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/weixin_46785057/article/details/167919596