【题解】[USACO19DEC]Milk Visits G

\(\text{Solution:}\)

这题不要把思想局限到线段树上……这题大意就是求路径经过的值中\(x\)的出现性问题。

最开始的想法是值域线段树……看了题解发现直接\(vector\)加二分即可\(O(n\log^2 n)\)解决。

思路：

用\(vector\)存下颜色\(i\)所出现的所有节点，对每一个\(vector\)排序后，考虑跳链的过程中二分第一个大于链头\(dfs\)序的点并判断它是不是在当前查询区间的范围内。最终复杂度是跳链的\(log\)和二分的\(\log.\)

#include<bits/stdc++.h>

using namespace std;

const int MAXN=2e5+10;

int top[MAXN],id[MAXN],rk[MAXN],son[MAXN],siz[MAXN],pa[MAXN];

int head[MAXN],tot,cnt,rt,n,m,dep[MAXN],ls[MAXN],rs[MAXN],val[MAXN];

struct E{int nxt,to;}e[MAXN];

vector<int>v[MAXN];

inline void add(int x,int y){e[++tot]=(E){head[x],y};head[x]=tot;}

void dfs1(int x,int fa){

	pa[x]=fa,siz[x]=1,dep[x]=dep[fa]+1;

	for(int i=head[x];i;i=e[i].nxt){

		int j=e[i].to;

		if(j==fa)continue;

		dfs1(j,x);siz[x]+=siz[j];

		if(siz[j]>siz[son[x]])son[x]=j;

	}

}

void dfs2(int x,int t){

	top[x]=t,rk[id[x]=++cnt]=x;

	if(!son[x])return;

	dfs2(son[x],t);

	for(int i=head[x];i;i=e[i].nxt){

		int j=e[i].to;

		if(j!=pa[x]&&j!=son[x])dfs2(j,j);

	}

}

void dfs3(int x){

	v[val[x]].push_back(id[x]);

	for(int i=head[x];i;i=e[i].nxt){

		int j=e[i].to;

		if(j==pa[x])continue;

		dfs3(j);

	}

}

void solve(int x,int y,int c){

	int fg=0;

	while(top[x]!=top[y]){

		if(dep[top[x]]<dep[top[y]])swap(x,y);

		vector<int>::iterator it=lower_bound(v[c].begin(),v[c].end(),id[top[x]]);

		if(it!=v[c].end()&&*it<=id[x])fg=1;

		x=pa[top[x]];

	}

	if(dep[x]<dep[y])swap(x,y);

	vector<int>::iterator it=lower_bound(v[c].begin(),v[c].end(),id[y]);

	if(it!=v[c].end()&&*it<=id[x])fg=1;

	printf("%d",fg);

}

int main(){

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;++i)scanf("%d",&val[i]);

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

		int x,y;

		scanf("%d%d",&x,&y);

		add(x,y);add(y,x);

	}

	dfs1(1,0);dfs2(1,1);dfs3(1);

	for(int i=1;i<=n;++i)sort(v[i].begin(),v[i].end());

	for(int i=1;i<=m;++i){

		int x,y,z;

		scanf("%d%d%d",&x,&y,&z);

		solve(x,y,z);

	}

	return 0;

}

巴特西

【题解】[USACO19DEC]Milk Visits G

最新文章

热门文章