图论水题2

div2 361 D. Tree Requests

题意

对于一颗$n$节点的树，每个节点有一个字母，有$m$次询问，每次询问求对于顶点$v$的子树中深度为$h$的结点能否组成一个回文串$ (1 \leq n \leq m \leq 5 \cdot 10^5) $

思路

• 关于$v$的子树结点，可以通过$dfs$序确定，那么对于特定$h$深度的子树节点，我们可以按深度将结点的入栈时间存起来之后用$dfs$序求出
• 关于能否组成回文串，只需要这些节点中出现奇数次的字母不大于1即可，所以我们对所有深度的节点维护一个前缀异或和，每次查询满足要求的子树结点(一定是连续的)的字母出现奇数次的个数即可，需要注意的是求前缀异或和时先加入了0，为了使下标对应将所有深度数组也先加入0
• 对于$v$节点的子树，其子树节点$x$满足 $ in[v] \leq in[x] < out[v] $

代码

#include<bits/stdc++.h>

#define ull unsigned long long 
#define ll long long
#define inf 1e9
#define INF 1e18
#define lc p<<1
#define rc p<<1|1
#define endl '\n'
#define all(a) a.begin()+1,a.end()
#define all0(a) a.begin(),a.end()
#define lowbit(a) (a&-a)
#define fi first
#define se second
#define pb push_back
#define yes cout<<"Yes"<<endl
#define no cout<<"No"<<endl

using namespace std;
const double eps=1e-6;
typedef pair<int,int>PII;
typedef array<int,3>PIII;
mt19937_64 rnd(time(0));  

const int N=5e5+10;
vector<int>e[N];
vector<int>mark[N];
vector<int>dep[N];


void solve()
{
	int n,m;
	cin>>n>>m;
	
	for(int i=2;i<=n;i++)
	{
		int x;cin>>x;
		e[x].pb(i);
	}
	
	string s;cin>>s;
	s=" "+s;
	
	int dfn=1;
	vector<int>in(n+1),out(n+1);
	
	for(int i=1;i<=n;i++)
	{
		mark[i].pb(0);
		dep[i].pb(0);
	}
	
	auto dfs=[&](auto && dfs,int u,int deep)->void
	{
		
		in[u]=dfn++;
		mark[deep].pb(mark[deep].back()^(1<<(s[u]-'a')));
		dep[deep].pb(in[u]);
		for(auto ed:e[u])
		{
			dfs(dfs,ed,deep+1);
		}
		out[u]=dfn-1;
	};
	
	dfs(dfs,1,1);
	
	auto count=[&](int x)
	{
		int cnt=0;
		while(x)
		{
			cnt++;
			x-=lowbit(x);
		}
		return cnt;
	};
	while(m--)
	{
		int v,h;
		cin>>v>>h;
		
		int l=lower_bound(all0(dep[h]),in[v])-dep[h].begin();
		int r=upper_bound(all0(dep[h]),out[v])-dep[h].begin();
		
		
		int cnt1=count(mark[h][r-1]^mark[h][l-1]);
		if(cnt1>1) no;
		else yes;
		
	}
	
}
	
	
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	solve();
	
	return 0;
}

div3 617 E1. String Coloring (easy version)

题意

给定一个字符串，你可以对每个字符进行染色$(0,1)$,染色完毕之后可以交换次相邻且颜色不同的字符，求是否存在一种染色方案使得字符串可以变为升序非降序排列

思路

显然若存在逆序对$(i,j)$则$i$与$j$一定是两种不同的颜色，我们对所有的逆序对进行连边之后跑二分图染色即可

代码

#include<bits/stdc++.h>

#define ull unsigned long long 
#define ll long long
#define inf 1e9
#define INF 1e18
#define lc p<<1
#define rc p<<1|1
#define endl '\n'
#define all(a) a.begin()+1,a.end()
#define all0(a) a.begin(),a.end()
#define lowbit(a) (a&-a)
#define fi first
#define se second
#define pb push_back
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl

using namespace std;
const double eps=1e-6;
typedef pair<int,int>PII;
typedef array<int,3>PIII;
mt19937_64 rnd(time(0));  

const int N=1010;
vector<int>e[N];

void solve()
{
	int n;cin>>n;
	string s;cin>>s;
	s=" "+s;
	
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			if(s[j]<s[i])
			{
				e[j].pb(i);
				e[i].pb(j);
			}
		}
	}
	
	vector<int>color(n+1);
	
	auto dfs=[&](auto &&dfs,int u,int c)->bool
	{
		color[u]=c;
		for(auto ed:e[u])
		{
			if(!color[ed] && !dfs(dfs,ed,3-c)) return false;
			else if(color[ed]==c) return false;
		}
		return true;
	};
	
	for(int i=1;i<=n;i++)
	{
		if(!color[i] && !dfs(dfs,i,1)) {no;return;}
	}
	yes;
	for(int i=1;i<=n;i++) cout<<color[i]-1;
	
}
	
	
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	solve();
	
	return 0;
}