看题解才切掉的菜题
[USACO19DEC]Milk Visits S
使用并查集求树上连通块 对于两个端点 如果在同一连通块中，则只能喝到这个连通块的牛奶 如果在不同连通块中，那么一定会穿过两种牛奶区（始末异，显然；始末同，中间一定会穿过一片异，否则始末会在同一连通块中）
#include<bits/stdc++.h> using namespace std; #define in Read() int in{ int i=0,f=1;char ch=0; while(!isdigit(ch)&&ch!='-') ch=getchar(); if(ch=='-') ch=getchar(),f=-1; while(isdigit(ch)) i=(i<<1)+(i<<3)+ch-48,ch=getchar(); return i*f; } const int N=1e5+5; int n,m,f[N]; int tot,first[N],nxt[N<<1],aim[N<<1]; bool col[N],ans;//H-true;G-false char s[N]; void ljb(int u,int v){ ++tot; nxt[tot]=first[u]; first[u]=tot; aim[tot]=v; return; } int get(int x){return x==f[x]?x:f[x]=get(f[x]);} void DFS(int u,int fa){ if(col[u]==col[fa]){ int x=get(u),y=get(fa); f[x]=y; } for(int e=first[u];e;e=nxt[e]){ int v=aim[e]; if(v==fa) continue; DFS(v,u); } return; } int main(){ n=in,m=in; scanf("%s",s+1); for(int i=1;i<=n;++i){ if(s[i]=='H') col[i]=true; else col[i]=false; } for(int i=1;i<n;++i){ int u=in,v=in; ljb(u,v); ljb(v,u); } for(int i=1;i<=n;++i) f[i]=i; DFS(1,0); for(int i=1;i<=m;++i){ int u=in,v=in;scanf("%s",s); u=get(u),v=get(v); if(u==v) ans=!((s[0]=='H')^col[u]); else ans=true; cout<<ans; } return 0; }