P5836 [USACO19DEC] Milk Visits S（树上并查集）

核心思路

对于相同颜色且相邻的点合并。

若不在同一集合，则0

若在同一集合，同色1 异色0

AC 代码

#include <bits/stdc++.h>   
using namespace std;  
int fa[1145141];
char col[1145141];
int n,m;
int find(int x)
{
	if(x==fa[x])	return x;
	return fa[x]=find(fa[x]);
}
void merge(int x,int y)
{
	fa[find(x)]=find(y);
}
int main() {  
    cin >> n >> m;  
    for (int i = 1; i <= n; i++) {  
        char a;
        cin>>a;
        fa[i] = i;
        col[i] = a;
    } 
    for (int i = 1; i < n; i++) {  
        int u, v;  
        cin >> u >> v;  
        if(col[u] == col[v]){
        	merge(u,v);
		}
    }  
    
    for (int i = 0; i < m; i++) {  
        int a, b;  
        char c;
        cin >> a >> b>>c;  
        if(find(a) == find(b)&&col[a] != c){
        	cout<<0;
		}
		else{
			cout<<1;
		}
    }  
  	
    return 0;  
}