脚本宝典收集整理的这篇文章主要介绍了洛谷 P5836 [USACO19DEC]Milk Visits S（树上预处理，st表），脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

传送门

解题思路

首先很显然的一种O(nLOGn)做法是st表：st[i][j][0/1/2]分别存从i开始向上走2^j步到达的节点编号/有没有H奶牛/有没有G奶牛。 代码量比较复杂。 还有一种很巧妙的做法是用top[i]表示i号点的奶牛种类从i向上最高可以到达的位置。 很显然假设读入询问的为x,y,c，答案为: (color[x]==c||color[y]==c||top[x]!=top[y]) 而top的处理与树剖很像:

• 当color[i]!=color[fa]时，top[i]=i;
• 当color[i]==color[fa]时，top[i]=top[fa];

AC代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorIThm>
using namespace std;
const int maxn=1e5+5;
int n,m,p[maxn],cnt,top[maxn];
char s[maxn];
struct node{
	int v,next;
}e[maxn*2];
void insert(int u,int v){
	cnt++;
	e[cnt].v=v;
	e[cnt].next=p[u];
	p[u]=cnt;
}
void DFs(int u,int fa){
	if(s[u]!=s[fa]) top[u]=u;
	else top[u]=top[fa];
	for(int i=p[u];i!=-1;i=e[i].next){
		int v=e[i].v;
		if(v==fa) continue;
		dfs(v,u);
	}
}
int main(){
	ios::sync_with_stdio(false);
	memset(p,-1,sizeof(p));
	cin>>n>>;m;
	for(int i=1;i<=n;i++){
		cin>>s[i];
	}
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		insert(u,v);
		insert(v,u);
	}
	dfs(1,0);
	for(int i=1;i<=m;i++){
		int x,y;
		char c;
		cin>>x>>y>>c; 
		if(s[x]==c||s[y]==c||top[x]!=top[y]) cout<<1;
		else cout<<0;
	}
	return 0;
}

脚本宝典总结

以上是脚本宝典为你收集整理的洛谷 P5836 [USACO19DEC]Milk Visits S（树上预处理，st表）全部内容，希望文章能够帮你解决洛谷 P5836 [USACO19DEC]Milk Visits S（树上预处理，st表）所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。